Amelia and Bedelia are competing in the game of Nim. Nim is a game in which there are ~N~ piles of stones in which the ~i~th pile contains ~a_i~ stones. On a player's turn, they may remove any positive number of stones, so long as all stones that player removes come from the same pile. The player who cannot move first loses.
However, since Amelia and Bedelia are both perfect logicians, they each figure out the solution to Nim fairly quickly and now they do not think it is very fun anymore. To make it more challenging, they introduce the following rule: After a player has moved, if the board is not symmetric, then the player who just moved loses immediately. The board is symmetric if the first nonempty pile has the same number of stones as the last non-empty pile, the second has the same number of stones as the second last, and so on. Note, empty piles are treated as if they do not exist. Just like normal Nim, if a player takes the last stone, they win.
Amelia and Bedelia plan to play ~T~ games to determine who is the superior player. In every game, Amelia will make the first move. If both players play optimally, who wins each game?
The first line contains a single integer ~T~, the number of missions per test case, ~(1 \le T \le 100)~
The inputs for the ~T~ games follow.
The first line of each game input contains a single integers, ~N~, ~(1 \le N \le 3 \cdot 10^5)~
The next line will contain ~N~ integers, representing the size of each pile from left to right, ~(1 \le a_i \le 10^9)~
For each game, output the winner of the game, either
Subtask 1 [30%]
~N \leq 5~
Subtask 2 [70%]
No additional constraints.
2 3 1 2 3 1 1