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-----

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-----

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


-----Example-----
Input
5
10
0001111111
4
0101
8
11001101
10
1110000000
1
1

Output
0001111111
001
01
0
1



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

Difficulty: interview

Starter code:

Solutions:
for _ in range(int(input())):
    # a, b = map(int, input().split())
    n = int(input())
    # arr = list(map(int, input().split()))
    s = input()
    l = 0
    r = n - 1
    if s.count('0') == n:
        print(s)
        continue
    if s.count('1') == n:
        print(s)
        continue
    while s[l] == '0':
        l += 1
    while s[r] == '1':
        r -= 1
    if r <= l:
        print(s)
        continue
    print(l * '0' + '0' + (n - r - 1) * '1')

ans = []
for _ in range(int(input())):
    n = int(input())
    u = list(map(int, list(input())))
    for i in range(n):
        if u[i] == 1:
            i1 = i
            break
    else:
        ans.append(''.join(map(str, u)))
        continue
    for i in range(n - 1, -1, -1):
        if u[i] == 0:
            i2 = i
            break
    else:
        ans.append(''.join(map(str, u)))
        continue
    if i2 < i1:
        ans.append(''.join(map(str, u)))
        continue
    u1 = '0' * i1 + '0' + '1' * (n - i2 - 1)
    ans.append(u1)
print('\n'.join(ans))


def solve():
    n = int(input())
    st = input()
    pref0 = 0
    for i in st:
        if i == "0":
            pref0 += 1
        else:
            break
    post1 = 0
    for i in st[::-1]:
        if i == "1":
            post1 += 1
        else:
            break
    if n != post1 + pref0:
        print(pref0 *"0"+"0"+post1*"1")
    else:
        print(pref0 * "0" + post1 * "1")
for i in range(int(input())):
    solve()

#list(map(int,input().split()))
t=int(input())
for _ in range(t):
    n=int(input())
    s=input()
    co=0
    for i in range(n):
        if(s[i]=='1'):
            break
        print('0',end="")
        co+=1
    ind=n
    
    for i in range(n-1,-1,-1):
        if(s[i]=='0'):
            break
        ind=i
    if(co-1<ind-1):
        print('0',end="")
    for i in range(ind,n):
        print('1',end="")
    print()
    
    
    


for test_i in range(int(input())):
    n = int(input())
    s = input()
    l1 = 0
    while l1 < n:
        if s[-l1 - 1] == '1':
            l1 += 1
        else:
            break
    l0 = 0
    while l0 < n:
        if s[l0] == '0':
            l0 += 1
        else:
            break
    if l0 + l1 < len(s):
        print('0' * (l0 + 1) + '1' * l1)
    else:
        print('0' * l0 + '1' * l1)

import sys
input = sys.stdin.readline

Q = int(input())
Query = []
for _ in range(Q):
    N = int(input())
    S = input().rstrip()
    Query.append((N, S))

for N, S in Query:
    i1 = N
    while i1 > 0 and S[i1-1] == "1":
        i1 -= 1
    i2 = -1
    while i2 +1< N-1 and S[i2+1] == "0":
        i2 += 1
    
    if i2 + 1 == i1:
        tmp = ""
    else:
        tmp = "0"
    ans = "0"*(i2+1) + tmp + "1"*(N-i1)
    print(ans)

import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
# import numpy as np
sys.setrecursionlimit(int(pow(10,6)))
# sys.stdin = open("input.txt", "r")
# sys.stdout = open("output.txt", "w")
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

# @lru_cache(None)
term=l()[0]
# term=1

for _ in range(term):
    n=l()[0]
    s=list(input())
    i=0
    while(i<n and s[i]!="1"):
        i+=1
    j=n-1
    while j>=0 and s[j]!="0":
        j-=1
    if(i<j+1):
        del(s[i:j])
    print("".join(s))

for nt in range(int(input())):
	n = int(input())
	s = input()
	if "1" not in s:
		print (s)
		continue
	ans = ""
	for i in range(n):
		if s[i]=="0":
			ans += s[i]
		else:
			ind = i
			break
	temp = ""
	for i in range(n-1,ind-1,-1):
		if s[i]=="0":
			ans += "0"
			break
		else:
			temp += "1"
	ans += temp
	print (ans)


from sys import stdin, stdout
import math

t = int(stdin.readline())
for _ in range(t):
    n = int(stdin.readline())
    s = stdin.readline().strip()
    st, end = float('inf'), -1
    for i in range(n):
        if s[i] == '1':
            st = i
            break

    for i in range(n-1, -1, -1):
        if s[i] == '0':
            end = i
            break

    if st < end:
        print(s[:st]+'0'+s[end+1:])
    else:
        print(s)




from itertools import groupby as gb

t = int(input())

for _ in range(t):
    n = int(input())
    s = input()
    if s.count('10') == 0:
        print(s)
        continue
    res = ""
    suf = ""
    l = [(k, len(list(v))) for k, v in gb(s)]
    if len(l) > 0 and l[0][0] == '0':
        res += l[0][0] * l[0][1]
        l = l[1:]
    if len(l) > 0 and l[-1][0] == '1':
        suf = l[-1][0] * l[-1][1]
        l = l[:-1]
    print(res + '0' + suf)


import math


def main():
    n = int(input())
    line = input()
    zero = 0
    one = 0
    i = 0
    while i < n and line[i] == '0':
        zero += 1
        i += 1
    i = n - 1
    while i > -1 and line[i] == '1':
        one += 1
        i -= 1
    zr = False
    on = False
    for i in range(n):
        if line[i] == '0':
            zr = True
    for i in range(n - 1, -1, -1):
        if line[i] == "0":
            on = True
        if line[i] == "1" and on:
            zero += 1
            break
    if zero == 0 and one == 0:
        if zr:
            print(0)
        else:
            print(1)
    else:
        line = ""
        for k in range(zero):
            line += "0"
        for k in range(one):
            line += "1"
        print(line)

def __starting_point():
    t = int(input())
    for i in range(t):
        main()

__starting_point()

for _ in range(int(input())):
    n = int(input())
    s = input()
    if n == 1:
        print(s)
        continue
    zero = -1
    one = -1
    for i in range(n):
        if s[i] == "0":
            zero = i
        if s[i] == "1" and one < 0:
            one = i
    if zero < one or one == -1 or zero == -1:
        print(s)
    else:
        print((one+1) * "0" + (n-zero-1) * "1")


# Contest No.: 652
# Problem No.: B
# Solver:      JEMINI
# Date:        20200623

import sys
import heapq

def main():
    t = int(input())
    for _ in range(t):
        n = int(sys.stdin.readline().strip())
        s = sys.stdin.readline().strip()
        if ("1" in s and "0" not in s) or ("1" not in s and "0" in s):
            print(s)
            continue
        lPoint = 0
        while s[lPoint] == "0":
            lPoint += 1
        rPoint = n - 1
        while s[rPoint] == "1":
            rPoint -= 1
        
        if lPoint > rPoint:
            print(s)
            continue
        
        if lPoint != n - 1:
            ans = s[:lPoint]
        else:
            ans = ""
        
        ans += "0"

        if rPoint != n - 1:
            ans += s[rPoint + 1:]
        print(ans)
        

    return

def __starting_point():
    main()
__starting_point()

import sys
input = sys.stdin.readline

t=int(input())
for tests in range(t):
    n=int(input())
    S=input().strip()

    OPENING=-1
    for i in range(n):
        if S[i]=="1":
            OPENING=i
            break

    ENDING=n
    for i in range(n-1,-1,-1):
        if S[i]=="0":
            ENDING=i
            break

    if OPENING==-1 or ENDING==n:
        print(S)
    elif OPENING>ENDING:
        print(S)
    else:
        print("".join(map(str,[0]*(OPENING+1)+[1]*(n-1-ENDING))))
        


for _ in range(int(input())):
    #n, m = map(int, input().split())
    #A = list(map(int, input().split()))
    n = int(input())
    s = input()
    if s == '0' * n or s == '1' * n:
        print(s)

    else:

        i = 0
        while s[i] == '0':
            i += 1
        j = n - 1
        while s[j] == '1':
            j -= 1
        if '1' in s[i:j + 1] and '0' in s[i:j + 1]:
            print(s[:i] + '0' + s[j + 1:])
        else:
            print(s)