A. We Need the Zero

time limit per test

1 second

memory limit per test

256 megabytes

There is an array aa consisting of non-negative integers. You can choose an integer xx and denote bi=ai⊕xbi=ai⊕x for all 1≤i≤n1≤i≤n, where ⊕⊕ denotes the bitwise XOR operation. Is it possible to choose such a number xx that the value of the expression b1⊕b2⊕…⊕bnb1⊕b2⊕…⊕bn equals 00?

It can be shown that if a valid number xx exists, then there also exists xx such that (0≤x<280≤x<28).

Input

Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤10001≤t≤1000). The description of the test cases follows.

The first line of the test case contains one integer nn (1≤n≤1031≤n≤103) — the length of the array aa.

The second line of the test case contains nn integers — array aa (0≤ai<280≤ai<28).

It is guaranteed that the sum of nn over all test cases does not exceed 103103.

Output

For each set test case, print the integer xx (0≤x<280≤x<28) if it exists, or −1−1 otherwise.

Example

Input

Copy

5

3

1 2 5

3

1 2 3

4

0 1 2 3

4

1 2 2 3

1

1

Output

Copy

6
0
3
-1
1

Note

In the first test case, after applying the operation with the number 66 the array bb becomes [7,4,3][7,4,3], 7⊕4⊕3=07⊕4⊕3=0.

There are other answers in the third test case, such as the number 00.

解题说明：此题是一道数学题，题目意思是是否存在一个数x使 a1^x^a2^x^a3^x...an^x=0。首先求出a1^a2..^an的值，然后判断n的奇偶性，奇数则就是该值，因为两个相同的数相与为0.如果n为偶数，则偶数个x本来相与就为0，只能判断a1^a2..^an结果是否为0，如果不是0，则不存在这样的值。

#include <stdio.h>int main()
{int t;scanf("%d", &t);while (t--) {int j, n, a, acc_xor = 0;scanf("%d", &n);for (j = 0; j < n; ++j){scanf("%d", &a);acc_xor ^= a;}if (n & 1){printf("%d\n", acc_xor);}else if (acc_xor == 0) {printf("0\n");}else{printf("-1\n");}}return 0;
}