AccurateLee
Contest: Codeforces Round 652 (Div. 2)
Difficulty rating: 1200
Tags: greedy, implementation, strings

Lee was cleaning his house for the party when he found a messy string under the carpets. Now he'd like to make it clean accurately and in a stylish way...

The string $$$s$$$ he found is a binary string of length $$$n$$$ (i. e. string consists only of 0-s and 1-s).

In one move he can choose two consecutive characters $$$s_i$$$ and $$$s_{i+1}$$$, and if $$$s_i$$$ is 1 and $$$s_{i + 1}$$$ is 0, he can erase exactly one of them (he can choose which one to erase but he can't erase both characters simultaneously). The string shrinks after erasing.

Lee can make an arbitrary number of moves (possibly zero) and he'd like to make the string $$$s$$$ as clean as possible. He thinks for two different strings $$$x$$$ and $$$y$$$, the shorter string is cleaner, and if they are the same length, then the lexicographically smaller string is cleaner.

Now you should answer $$$t$$$ test cases: for the $$$i$$$-th test case, print the cleanest possible string that Lee can get by doing some number of moves.

Small reminder: if we have two strings $$$x$$$ and $$$y$$$ of the same length then $$$x$$$ is lexicographically smaller than $$$y$$$ if there is a position $$$i$$$ such that $$$x_1 = y_1$$$, $$$x_2 = y_2$$$,..., $$$x_{i - 1} = y_{i - 1}$$$ and $$$x_i < y_i$$$.

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

Next $$$2t$$$ lines contain test cases — one per two lines.

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

The second line contains the binary string $$$s$$$. The string $$$s$$$ is a string of length $$$n$$$ which consists only of zeroes and ones.

It's guaranteed that sum of $$$n$$$ over test cases doesn't exceed $$$10^5$$$.

Output format:
Print $$$t$$$ answers — one per test case.

The answer to the $$$i$$$-th test case is the cleanest string Lee can get after doing some number of moves (possibly zero).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, Lee can't perform any moves.

In the second test case, Lee should erase $$$s_2$$$.

In the third test case, Lee can make moves, for example, in the following order: 11001101 $$$\rightarrow$$$ 1100101 $$$\rightarrow$$$ 110101 $$$\rightarrow$$$ 10101 $$$\rightarrow$$$ 1101 $$$\rightarrow$$$ 101 $$$\rightarrow$$$ 01.

Example input:
5
10
0001111111
4
0101
8
11001101
10
1110000000
1
1

Example output:
0001111111
001
01
0
1

Editorial:
$$$\mathcal Complete\; \mathcal Proof$$$ :
Realize that the answer is always non-descending, and we can't perform any operations on non-descending strings.
First we know that we can't perform any operations on non-descending strings, so the answer to a non-descending string is itself. From now we consider our string $$$s$$$ to not to be non-descending. (i.e. there exist index $$$i$$$ such that $$$1 \le i \le n-1$$$ and $$$s_i > s_{i+1}$$$)
Also realize that the remaining string wont be empty, so "0" is the cleanest possible answer, but we can't reach it probable.
Now realize that leading zeroes and trailing ones can't be present in any operation. So they have to be in the answer, erase them from $$$s$$$, and add them to the answer for the modified $$$s$$$. From now we know that the string $$$s$$$ has no leading zeroes and/or trailing ones, and is not non-descending, so it starts with $$$1$$$ and ends with $$$0$$$. (why?)
With some small paperwork, we will realize that the answer to a string that starts with $$$1$$$ and ends with $$$0$$$ is a single $$$0$$$(proof is bellow). So if the string $$$s$$$ is non-descending and it has $$$x$$$ leading zeroes and $$$y$$$ trailing ones($$$x$$$ and $$$y$$$ can be equal to zero), then the answer is $$$\underbrace{0\,0\dots0}_{x}\,0\,\underbrace{1\,1\dots1}_{y}$$$ (its $$$x+1$$$ zeroes and $$$y$$$ ones in order)
$$$\mathcal The\;\mathcal Small\;\mathcal Paperwork:$$$
We will randomly perform operations until we can't do any more or the string's length is equal to $$$2$$$, but we wont erase the first $$$1$$$ and the last $$$0$$$, we want to prove that the remaining string's length is exactly $$$2$$$ after the process ends, proof by contradiction :
So it's length is at least $$$3$$$, so we have at least two $$$1$$$ or at least two $$$0$$$. If we had two or more $$$0$$$ then the string $$$[s_1\,s_2\dots s_{n-1}]$$$ will not be non-descending(so we can perform more operations as we proved in STAR, but the process have ended, contradiction!) and if we had two or more $$$1$$$ then the string $$$[s_2\,s_3\dots s_n]$$$ will not be non-descending. So the length of the remaining string is exactly $$$2$$$, and we haven't erased first '1' and last '0', so the string is equal to "10", now erase '1' to get the cleanest string.
Sorry if the proof seems too long and hard, i wanted to explain it accurately. ^-^