Read problems statements in Mandarin chinese, Russian and Vietnamese as well.

Chef recently discovered a function $XOR()$, which computes the XOR of all elements of a sequence:
$$XOR(a_{1..n}) = a_{1} \oplus a_{2} \oplus \dots \oplus a_{n}\,.$$

Chef has a sequence $A$ with size $N$. He generated a new sequence $B$ with size $N^{2}$ using the following formula:
$$B_{iN+j+1} = (A_{i+1} + A_{j+1}) \quad \forall\; 0 ≤ i, j < N\,.$$

Compute the value of $XOR(B)$.

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \dots, A_{N}$.

------ Output ------
For each test case, print a single line containing one integer — the answer to the problem.

------ Constraints ------
$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{5}$
$2^{0} ≤ A_{i} < 2^{30}$ for each valid $i$

------ Subtasks ------

Subtask #1 (30 points):
$1 ≤ N ≤ 500$
$2^{0} ≤ A_{i} < 2^{10}$ for each valid $i$

Subtask #2 (70 points): $1 ≤ N ≤ 10^{5}$

----- Sample Input 1 ------
1
2
1 2
----- Sample Output 1 ------
6
----- explanation 1 ------
Example case 1: The sequence $B$ is $\{A_{1} + A_{1}, A_{1} + A_{2}, A_{2} + A_{1}, A_{2} + A_{2}\} = \{2, 3, 3, 4\}$. The XOR of its elements is $B_{1} \oplus B_{2} \oplus B_{3} \oplus B_{4} = 6$.

见题面

见题面