Trọng có một thành phần ngon miệng – một số nguyên K. Anh ấy định nghĩa một ma trận ngon miệng A có N hàng (đánh số từ 1 tới N) và M cột (đánh số từ 1 tới M) là ~A_{i,j}~ = K + i + j với mọi i, j.

Hiện tại, Trọng đang bận ở trong bếp để làm ma trận ngon miệng này. Giúp anh ấy tìm phép XOR của tất cả các phần tử trong ma trận.

Dữ liệu vào

• Dòng đầu tiên của dữ liệu vào chứa một số nguyên T – số test. T test được mô tả như sau:
• Dòng đầu tiên cũng là dòng duy nhất của mỗi test chứa ba số nguyên N, M và K

Dữ liệu ra

Với mỗi test, in ra một dòng chứa một số nguyên – kết quả phép XOR của tất cả các phần tử trong ma trận

Ràng buộc

• 1 ≤ T ≤ ~10^5~
• 1 ≤ N, M ≤ 2 × ~10^6~
• 1 ≤ K ≤ ~10^9~
• Tổng của N trong tất cả các test không vượt quá 2 × ~10^6~
• Tổng của M trong tất cả các test không vượt quá 2 × ~10^6~

Ví dụ

Input

2 
2 2 5 
2 3 7

Output

14 
5

Giải thích

Ví dụ 1: Ma trận là

=~\begin{pmatrix} 5+1+1 & 5+1+2 \\ 5+2+1 & 5+2+2 \end{pmatrix} = \begin{pmatrix} 7 & 8 \\ 8 & 9 \end{pmatrix}~

Phép XOR của tất cả các phần tử là 7 ⊕ 8 ⊕ 8 ⊕ 9 = 14.

Ví dụ 2: Ma trận là

=~\begin{pmatrix} 7+1+1 & 7+1+2 & 7+1+3\\ 7+2+1 & 7+2+2 & 7+2+3 \end{pmatrix} = \begin{pmatrix} 9 & 10 & 11\\ 10 & 11 & 12 \end{pmatrix}~

Phép XOR của tất cả các phần tử là 9 ⊕ 10 ⊕ 11 ⊕ 10 ⊕ 11 ⊕ 12 = 5.