Nim-like game

Problem code: HS09NLG

Consider the following game similar to Nim. Two players use N stacks of stones. A move consists of taking away a positive number of stones from a chosen stack. For each stack, the first move which involves taking stones from this stack, should leave at least one stone on the stack. In any subsequent move using this stack, a player can take at most twice as many stones as in the previous move on this stack.

Players take turns to move. The one who cannot make a move loses. Write a program which determines if for a given set of starting sizes of stacks the player who moves first can force a win.

Input

In the first line of input there is one integer C (1 ≤C ≤ 1 000), meaning the number of test cases. Each test case is described in two lines. The first line of the two contains a number N (1 ≤N ≤ 1 000) and the second contains N numbers describing the sizes of stacks. No stack contains more than 300 stones.

Output

For each testcase write out the number 1 if the starting player can always win, or 0 in the opposite case.

Example

Input:
2
1
5
2
2 4
Output:
0
1

Scoring

For solving this problem you will score 10 points.