E. Save Me!
time limit per test
7 seconds
memory limit per test
16 megabytes
input
standard input
output
standard output

Note that the memory limit is unusual.

Help, I've been trapped in a magical seal!

There is an array $$$a$$$ with $$$n$$$ integers. In one operation, you can choose $$$1\le i\le n - 1$$$ and either:

  • Set $$$a_i := a_i \oplus a_{i+1}$$$$$$^{\text{∗}}$$$.
  • Set $$$a_{i+1} := a_i \oplus a_{i+1}$$$.

The seal becomes broken as soon as there is an index $$$i$$$ such that $$$a_i = 0$$$. Determine the minimum number of operations required to break the seal, or output $$$-1$$$ if you can never escape!

$$$^{\text{∗}}$$$$$$\oplus$$$ denotes the bitwise XOR operation.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1\le n\le 100$$$) — the number of elements in the array.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \lt 2^{25}$$$) — the elements of $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$100$$$.

Output

For each testcase, output a single integer: the minimum number of operations required to break the seal, or $$$-1$$$ if it is impossible.

Example
Input
5
3
1 2 1
4
4 2 3 1
5
1 2 4 8 16
3
0 1 2
1
1234
Output
3
2
-1
0
-1
Note

In the first example, we may do the following sequence of operations:

  1. Set $$$a_1 := a_1 \oplus a_2 = 3$$$: the new array is $$$[3, 2, 1]$$$.
  2. Set $$$a_2 := a_1 \oplus a_2 = 1$$$: the new array is $$$[3, 1, 1]$$$.
  3. Set $$$a_3 := a_2 \oplus a_3 = 0$$$: the new array is $$$[3, 1, 0]$$$ and the seal is broken.

In the third example, we can prove that no sequence of operations breaks the seal.