E. XOR to Zero
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of $$$n$$$ non-negative integers.

You want to make all elements of the array equal to $$$0$$$.

In one operation, you can choose an index $$$i$$$ ($$$1 \le i \le n$$$). Let $$$S$$$ be the XOR of all elements $$$a_j$$$ such that $$$a_j \ne a_i$$$.

If there is no such index $$$j$$$, then $$$S = 0$$$.

After that, you replace $$$a_i$$$ with $$$S$$$.

Your task is to determine the minimum number of operations needed to make all elements equal to $$$0$$$.

If it is impossible, print $$$-1$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \lt 2^{30}$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print a single integer — the minimum number of operations needed to make all elements equal to $$$0$$$, or $$$-1$$$ if it is impossible.

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