#216162. [ICPC 2023 NAC] Splitting Pairs

Alice and Bob are playing a modified game of Nim. Initially, there are some non-empty piles of stones in front of them. They take turns, and Alice takes the first turn.

On a single turn, a player must do the following actions in order:

• Remove some number of piles of stones — at least one but no more than half the number of piles.
• Choose the same number of piles of remaining stones, and split each of those piles into two non-empty piles.

Notice that after each valid move, there should be the same number of non-empty piles of stones as at the start of the game. A player who cannot perform all the actions on their turn loses the game.

You are given many games, and for each one, you’d like to determine who would win if both players play optimally.

The first line of input contains an integer (), which is the number of games Alice and Bob play.

Each game is represented on two lines. The first line of each game contains an integer (), which is the number of piles of stones.

The next line of the game contains space-separated integers (), which are the number of stones in each pile.

Output lines. For each game, output a single line with a single integer, which is if Alice wins and if Bob wins. Assume Alice takes the first turn, and both players play optimally. Output the game results in the order the games appear in the input.

样例输入 1

4
3
1 1 1
3
1 1 2
3
2 2 2
4
4 4 4 4

样例输出 1

0
1
0
1