Balanced Reversals ~ WildLife-TK

Chef is given a binary string

$A$ of length $N$ . He can perform the following operation on $A$ any number of times:

Choose $L$ and $R$ $(1 \leq L \leq R \leq N)$ , such that, in the substring $A [L, R]$ , the number of $1$ s is equal to the number of $0$ s and reverse the substring $A [L, R]$ .

Find the lexicographically smallest string that Chef can obtain after performing the above operation any (possibly zero) number of times on $A$ .

String $X$ is lexicographically smaller than string $Y$ , if either of the following satisfies:

$X$ is a prefix of $Y$ and $X \neq Y$ .
There exists an index $i$ such that $X_{i} < Y_{i}$ and $X_{j} = Y_{j}, \forall j$ such that $1 \leq j < i$ .

Input Format

First line will contain $T$ , the number of test cases. Then the test cases follow. Each test case contains two lines.
The first line contains the integer $N$ , the length of the binary string.
The second line contains the binary string $A$ .

Output Format

For each test case, print the lexicographically smallest binary string that can be obtained after performing the operation any (possibly zero) number of times.

Constraints

$1 \leq T \leq 100$
$1 \leq N \leq 10^{5}$
Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$ .

Sample Input 1

Sample Output 1

00011
0000

Explanation

Test Case $1$ : Chef can choose $L = 2$ and $R = 5$ . The chosen substring, $A [2, 5] = 1100$ . On reversing this, we get $0011$ . Thus, the final string is $A = 00011$ . Note that this is the lexicographically smallest string possible.

Test Case $2$ : Since the string is already lexicographically minimum, Chef does not need to apply any operation.