Given a string $s$ of length $n$ consisting only of $0$s and $1$s, you can perform the following operation any number of times (possibly zero):

• Choose a substring whose first and last characters are different, and delete this substring.

For example, for $s = 0001110$, the substring $001$ has a different first and last character. After choosing and deleting this substring, the original string becomes $0110$.

After performing the operation any number of times, what is the lexicographically smallest possible string $s$?

† For two strings $s$ and $t$, let $i$ be the first position where the two strings differ. If $s_i$ is $0$ and $t_i$ is $1$, then $s$ is lexicographically smaller than $t$. If no such $i$ exists, the shorter string is lexicographically smaller. The empty string is lexicographically smaller than any other string.

Input

Each test file contains multiple test cases. The first line contains the number of test cases $T$ ($1 \le T \le 10^5$). The format for each test case is as follows:

The first line contains an integer $n$ ($1 \le n \le 10^6$), representing the length of the string. The second line contains a string $s$ of length $n$, consisting only of $0$s and $1$s.

It is guaranteed that the sum of $n$ over all test cases in each test file does not exceed $10^6$.

Output

For each test case, output a single line containing the lexicographically smallest string obtainable through the operations. Specifically, if the answer is an empty string, output "empty".

Examples

Input 1

4
2
01
4
0010
5
10011
5
11011

Output 1

empty
0
empty
11