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

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)$.

Example 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 total length 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$.