408855: GYM103351 E The Best Present

Daniyar is known to be a very friendly and organized boy and of course he did not forget about Vitya's birthday!

Last year his present for Vitya was a beautiful directed graph with $$$1000$$$ vertices and $$$10000$$$ edges. However, little did he know that Vitya hates graphs with more than $$$5000$$$ edges! He was very frustrated to find his present in a trash bin near Vitya's home.

This year, however, Daniyar is well-prepared. He has researched a lot of scientific papers and after a thorough investigation he has come to the conclusion that Vitya loves arrays consisting of two or more positive integers.

He has already bought a very pretty array and he is eager to go to Vitya's home and see his reaction after receiving such a nice present. His research, though, apparently was not deep enough, as his friend Batyr told him today that Vitya actually hates all arrays not satisfying $$$a_1 \oplus \ldots \oplus a_n = 0$$$!

Only several hours remain for Daniyar to solve this problem. He is a simple student so he cannot afford a new present array. What he can do instead is to increase any number in the array by $$$1$$$ and pay $$$1$$$ dollar for it. How much extra money does Daniyar need to spend to make Vitya finally enjoy his present?

The first line of the input contains a single integer $$$T$$$ — number of test cases ($$$1 \le T \le 50$$$). Each test case contains two lines of input.

First line of each test case contains a single integer $$$n$$$ — size of Daniyar's present array ($$$2 \le n \le 12$$$).

Second line of each test case contains $$$n$$$ space-separated integers $$$a_1, \ldots, a_n$$$ — the present array itself ($$$1 \le a_i \le 10^9$$$).

For each test case output a single integer on a separate line — the minimum amount of money Daniyar needs to spend to make Vitya finally enjoy his present.

3
2
3 8
3
15 16 1
4
1 4 10 11

5
2
2

$$$a \oplus b$$$ is a well-known bitwise operation called 'XOR'. It is denoted as '^' in C and C++. Some examples: $$$5 \oplus 7 = 2$$$, $$$1 \oplus 2 = 3$$$, $$$6 \oplus 3 = 5$$$.

In the first test case, Daniyar can fix his present by increasing the first number $$$a_1$$$ to $$$8$$$.

In the second test case, Daniyar can fix his present by increasing the first number $$$a_1$$$ to $$$17$$$.