Nim

Nim is a two-player game played with several piles of stones. The players alternate turns, and on a turn a player removes one or more stones from any single pile. Play ends when all the stones have been removed, and the last player to have moved wins. Given a position in Nim, determine how many winning moves there are in that position.

A position is called losing if the first player to move from it would lose under perfect play by both sides. A winning move is therefore a move that leaves the game in a losing position. A famous theorem classifies all losing positions. Suppose a Nim position has $n$ piles containing $k_1, k_2, \dots, k_n$ stones respectively; then there are $k_1 + k_2 + \dots + k_n$ possible moves. Write each $k_i$ in binary. Then the position is losing if and only if, among all the $k_i$, there is an even number of 1's in every digit position — equivalently, the position is losing if and only if the XOR of the $k_i$ is 0.

Consider the position with three piles $k_1 = 7$, $k_2 = 11$, and $k_3 = 13$. In binary these values are:

• 111
• 1011
• 1101

The rightmost digits contain an odd number of 1's, so this position is not losing. If $k_3$ were instead 12, every digit position would contain exactly two 1's and the position would become losing. Since a winning move is any move that leaves a losing position, removing one stone from the third pile is a winning move when $k_1 = 7$, $k_2 = 11$, and $k_3 = 13$. In fact there are exactly three winning moves from this position: remove one stone from any one of the three piles.

The input contains several test cases. Each test case begins with a line giving the number of piles $n$ ($1 \le n \le 1000$). The next line contains $n$ positive integers $k_i$ ($1 \le k_i \le 1{,}000{,}000{,}000$), the number of stones in each pile. The end of input is marked by a test case with $n = 0$, which must not be processed.

For each test case, output a single line containing the number of winning moves from the given Nim position.