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?

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\).

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

1
3
5 7 9

1