A. Maximal String
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a binary string of length $$$n$$$.

You can take two consecutive $$$1$$$s, remove them, and replace them with $$$0$$$.

Also, you can take two consecutive $$$0$$$s, remove them, and replace them with $$$1$$$.

You can do these operations any number of times (possibly zero).

You have to find the lexicographically largest string you can obtain.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

  • $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
  • In the first position $$$k$$$ where $$$a$$$ and $$$b$$$ differ (from left to right), the character $$$a_k$$$ is smaller than the character $$$b_k$$$
Input

The first line contains one integer $$$t$$$ $$$( 1 \le t \le 10^4):$$$ the number of test cases.

The first line of each test case contains one integer $$$n$$$ $$$(1 \le n \le 10^5):$$$ the length of the binary string $$$s$$$.

The second line of each test case contains a binary string consisting of $$$n$$$ characters.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\times 10^5$$$

Output

For each test case, output $$$t$$$ : the lexicographically largest string you can obtain.

Example
Input
6
6
000010
6
101000
6
011000
6
110101
14
01010101010100
14
10101010110101
Output
1110
110
110
110101
1
110101
Note
  • A binary string is a string consisting only of zeros and ones.
  • The character '0' is smaller than the character '1'.