XORs

You are given $n$ integers as $a_1$, $a_2$, $a_3$, $a_4$, …, $a_n$.

First of all, you have to find the XORs of all of the pairs that can be formed from the given integers. That means, $XOR(a_i, a_j)$ where $1 \le i, j \le n$ and $i < j$. Finally, your ultimate goal is to find the cumulative XOR of previously found XORs of each pair.

Input

Input starts with an integer $T$ ($0 < T \le 50$), denoting the number of test cases.

The first line of each test case contains an integer $n$ ($2 \le n \le 10^5$). The next line contains $n$ space separated integers $a_i$ ($1 \le i \le n$, $1 \le a_i \le 1000$).

Output

For each case, print a single line containing a single integer which denotes the final result.

Sample

Input	Output
2 2 3 4 5 1 2 2 4 5	7 0