Given $n + 1$ integers $a_0, \dots, a_n$.

For an integer $u$, let the positions of the bits that are $1$ in its binary representation be $k_1, k_2, \dots, k_m$. Its weight is defined as $f(u) = a_{k_1} \oplus a_{k_2} \oplus \dots \oplus a_{k_m}$. Here, the binary bit positions are numbered from right to left as $0, 1, 2, \dots$. The symbol $\oplus$ denotes the bitwise XOR operation.

You want to find how many integers $u$ in the range $0 \leq u \leq 2^n - 1$ satisfy $f(u) = f(u + 1)$. For convenience, please output the answer in binary form (without modulo).

Note: The output must not contain leading zeros, unless the answer is $0$.

Input

This problem contains multiple test cases.

The first line contains an integer $T$, representing the number of test cases.

The following lines contain the test cases. For each test case:

• The first line contains a positive integer $n$.
• The second line contains $n + 1$ integers $a_0, \dots, a_n$.

Output

For each test case, output a single line containing a binary integer representing the answer.

Reminder: The output must not contain leading zeros, unless the answer is $0$.

Examples

Input 1

5
2
0 1 2
3
1 3 3 1
4
2 2 5 4 2
5
7 0 3 4 0 1
6
5 2 1 8 6 0 9

Output 1

10
1
100
11
0

Note 1

For the first test case:

• $(0)_{10} = (0)_{2}$, so $f(0) = 0$;
• $(1)_{10} = (1)_{2}$, so $f(1) = a_0 = 0$;
• $(2)_{10} = (10)_{2}$, so $f(2) = a_1 = 1$;
• $(3)_{10} = (11)_{2}$, so $f(3) = a_0 \oplus a_1 = 0 \oplus 1 = 1$;
• $(4)_{10} = (100)_{2}$, so $f(4) = a_2 = 2$.

Among these, $f(0) = f(1)$ and $f(2) = f(3)$, so the output is $(2)_{10} = (10)_{2}$.

Constraints

Let $\sum n$ denote the sum of $n$ over all test cases in a single test file.

For all data, $1 \leq T \leq 10^3$, $1 \leq n \leq 2\times 10^5$, $\sum n \leq 6\times 10^5$, $0 \leq a_i \leq 2^{30} - 1$.