George and Kramer are in a serious fight. Seeing this, Jerry comes to convince them and settle the fight with a reasonable task. Knowing about their fondness of stamps, he creates a wonderful task for them. They are given N containers each having one or more stamps. Containers are numbered from 1 to N, where ith container has A[i] number of stamps. The game goes as follows. The first player will choose a container and take one or more stamps from it. Then, the second player will choose a non-empty container and take one or more stamps from it. And then they repeat this alternatively. This process will continue, until one of the players is not able to take any stamps, i.e., there are no stamps left. One who is not able to take any stamps loses the game. Note that player can choose only non-empty container.

Luckily George somehow got the first chance. He wants to know the number of ways to make a first move such that under optimal play, he wins. Being so poor at math and programming, he asks for your help. Help him!

Input Format:

The first line has an integer T, the number of test cases.

Then for each test case, the first line contains an integer N, i.e., number of containers and the second line contains N integers, i.e., number of stamps in each of the containers separated by a single space.

Output Format

Print the number of ways to make the first move such that under optimal play, George always wins. If he cannot win under optimal play, print 0.

Constraints

1 ≤ T ≤ 50

1 ≤ N ≤ 10⁶

1 ≤ A[i] ≤ 10⁹

Sample

Input:
1
2
2 3

Output:
1