F. A bitty problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ahmad is always tired.

He is so tired that he cannot make his small array beautiful :(

And by beautiful we mean that for $$$(2\le i\le n)$$$ $$$a_i \oplus a_{i-1}=X$$$ for some constant $$$X$$$.

By $$$\oplus$$$ we mean the well known xor operation.

You will be given Ahmad's array, what is the minimum number of bits you need to change so that Ahmad's array is beautiful?

Input

The first line contains a single integer $$$tc \: (1\le tc \le 1000)$$$ — the number of testcases.

The first line of each test case contains a single integer $$$n \: (3\le n\le 1000)$$$.

The next line contains $$$n$$$ integers $$$a_i \: (1\le a_i \le 1000) $$$.

Output

For each test case print one integer, the answer to the problem.

Example
Input
5
5
1 2 3 4 5
3
1 2 1
3
1 1 1
4
100 200 300 400
3
100 1 1
Output
4
0
0
7
4
Note

in the first test case we change $$$4$$$ bits and the array becomes [$$$1,2,1,2,1$$$] and xor of any two adjacent numbers is $$$3$$$.