You’re given a combinational logic circuit consisting of NAND gates. There are multiple binary inputs with a single binary output. The circuit is in the form of a full binary tree. All inputs are provided at the leaf nodes and every other node is a NAND logic gate.

Input Format
The first line of input consists of an integer t denoting the number of test cases. The first line of each test case consists of an integer h denoting the height of the tree. Second line of line of each test case consists of space separated binary inputs (0 or 1) denoting the inputs to the circuit.

Output Format
For each circuit print the output (0 or 1) found after feeding inputs into the circuit.

Sample Input
3
2
1 0
4
0 0 0 1 1 0 1 1
3
1 1 1 1
Sample Output
1
1
0
Truth table
A B NAND
0 0 1
0 1 1
1 0 1
1 1 0
Constraints
1 <= t <= 128
2 <= h <= 16

Explanation
For input

4
0 0 0 1 1 0 1 1
The tree constructed is below.

Solving the circuit one arrives at the output 1.