You are given a sequence $a_1, a_2, \dots, a_n$ of length $n$. Please construct an integer sequence $b_1, b_2, \dots, b_n$ such that:

• For all $i$, $b_i \ge a_i$.
• The sum of the sequence $b$ involves no carries in binary addition.
• Among all sequences satisfying the above two conditions, you need to minimize $\sum_{i=1}^n b_i$.

This problem involves multiple test cases.

Input

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

For each test case, the first line contains a positive integer $n$, representing the length of the sequence.

The next $n$ lines each contain a string consisting only of $\texttt{01}$, representing the binary representation of the numbers in the sequence. It is guaranteed that each string starts with $\texttt{1}$.

Output

For each test case, output a single line containing a binary number, representing the binary representation of $\sum_{i=1}^n b_i$.

Examples

Input 1

4
2
10
10
2
10100
1001
3
1
1
110
2
1101
101011

Output 1

110
11101
1011
111011

Note 1

For the first test case, $b=((100)_2, (10)_2)$.

For the second test case, $b=a$.

For the third test case, $b=((10)_2,(1)_2,(1000)_2)$.

For the fourth test case, $b=((10000)_2,(101011)_2)$.

Input 2

See the provided files.

Constraints

Let $\max L$ be the maximum length of the binary strings, $\sum L$ be the total length of all strings in a single test case, and $\sum^2 L$ be the sum of the squares of the lengths of all strings across all test cases.

For $100\%$ of the data, it is guaranteed that $T\le 10, 2\le n \le 10^5, 1\le \max L\le \sum L \le 10^5, 1\le \sum^2 L \le 10^6$.

| :---: | :---: | :---: | :---: | | Test Case ID | $n$ | $\max L$ | Special Constraints | | $1$ | .h=6 =2 | $\le 10$ | .h=10 | | $2$ | | $\le 20$ | | | $3$ | | $\le 50$ | | | $4$ | | $\le 300$ | | | $5$ | | $\le 10^3$ | | | $6$ | | $\le 10^5$ | | | $7$ | .h=2 $\le 8$ | $\le 8$ | | | $8$ | | $\le 50$ | | | $9$ | .h=2 .w=2 $\le 100$ | | | | $10$ | | | | | $11$ | .h=5 .w=2 $\le 10^3$ | | $\sum L \le 10^3$ | | $12$ | | | $\sum L \le 10^3$ | | $13$ | | | | | $14$ | | | | | $15$ | | | | | $16$ | .h=10 .w=2 $\le 10^5$ | | $\sum^2 L \le 3\times 10^5$, each binary number is a power of $2$ | | $17$ | | | Each binary number is a power of $2$ | | $18$ | | | Each binary number is a power of $2$ | | $19$ | | | $\sum^2 L \le 3\times 10^5$ | | $20$ | | | $\sum^2 L \le 3\times 10^5$ | | $21$ | | | $\sum^2 L \le 3\times 10^5$ | | $22$ | | | | | $23$ | | | | | $24$ | | | | | $25$ | | | |