Watson and Sherlock are playing the game of Nim.

The game of Nim is played as follows:

1) n heaps are given containing varying number of stones.
2) The two players take alternate turns in removing one or more number of stones from a heap.
3) The last player to remove the last set of stones win.

Given the configuration of heaps at any instant of game help Watson in counting the different moves he can make in one step , so that he finally wins the game.

Input: First line contain number of testcases t.

Each testcase consists of two lines:
The first line contains the number of heaps n.
The second line contains n separate integers , each denoting no. of stones in the ith pile.

Output: Print the no. of different moves that watson can make for each testcase.

constraints:

• $1 \le t \le 100$
• $1 \le n \le 1000000$
• $1 \le number_of _stones_in_a_heap \le 1000000$