Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

HS09NLG - Nim-like game

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.


Added by:Adam Dzedzej
Date:2009-09-16
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 C++ 4.3.2 CLOJURE ERL JS-RHINO NODEJS OBJC PERL6 SQLITE VB.NET
Resource:High School Programming League (thanks to Talent Association)

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.