Problem F: Stone Game

Problem F: Stone Game

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 895  Solved: 236
[Submit][Status][Web Board]

Description

Pisces and Nancy are playing a game. There are \(n\) piles of stones on the ground, and they take turns to select one pile and pick some stones (at least one) from the pile. The person who picks the last stone wins. Pisces goes first. How many ways are there for Pisces to pick stones in the first step with a guaranteed victory?

Input

The first line contains a single integer \(T(1\leq T\leq 10^3)\), which represents the number of the test cases.
In each of the test case, the first line contains a single integer \(n(1\leq n\leq 10^5)\). The second line contains \(n\) integers \(a_1, a_2,...,a_n(1\leq a_i\leq 10^6)\), which represent the number of stones in each pile. It is garanteed that the sum of \(n\) will not exceed \(7*10^5\).

Output

For each test case, print the answer in one line. If Pisces cannot win anyway, print 0.

Sample Input

1
3
5 7 9

Sample Output

1

HINT

[Submit][Status]