Problem Description

You are given $n + 1$ integers $a_0 \dots a_n$.

For an integer $u$, suppose the bit positions where its binary representation is $1$ are $k_1, k_2 \dots k_m$. Then its weight is $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.

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

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

Input Format

This problem contains multiple test cases.

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

Then the test cases follow. 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 Format

For each test case, output one line containing a binary integer, which is the answer.

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

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

10
1
100
11
0

Hint

"Sample Explanation #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 them, we have $f(0) = f(1)$ and $f(2) = f(3)$, so the output is $(2)_{10} = (10)_{2}$.

"Constraints"

Let $\sum n$ be the sum of $n$ within a single test file.

For all testdata, $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$.

Only if you pass all test points of this problem can you get the score for this problem.

Translated by ChatGPT 5