Divide or take away?

There are N piles of stones. In each move, you can either take any number of stones from a single pile or split a pile into two smaller piles. The player who takes the last stone wins the game.

Your task is to determine the winner, assuming both players use the optimal strategy: the player who makes the first move or the one who moves second.

Input

The first line contains the number of test cases T (1 <= T <= 100). Each test case consists of two lines: the first line contains the integer N, and the second line lists the number of stones in each pile S_i, separated by spaces.

1 <= N <= 10^3

1 <= S_i <= 10^6

Output

Output a single line with a sequence of T numbers, each being either 1 or 2, indicating the player who will win for each test case.

Examples