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 ≤ t ≤ 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 ≤ n ≤ 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 → 1100101 → 110101 → 10101 → 1101 → 101 → 01.
__author__ = 'Devesh Bajpai'

'''
https://codeforces.com/problemset/problem/1369/B

Solution: Working through a few examples we can observe the any substring of type 10 can reduce to 0.
But what cannot be reduced is the 0s before that substring and the 1s after it. That is because the
former don't have at least one 1 before them and the later don't have at least one 0 after them. 
So first we check if that substring of 10 type exist. If not, the string is returned as is. If yes,
we need to find the leading 0s and the trailing 1s. That extra 0 in the middle is due to the substring
of type 10 reducing to 0. 

Also, lets workout a substring of pattern 10 and see how it can be reduced to 0:

say, s = 00 11101010001000100 11111
Using space to demarcate the leading 0s and trailing 1s.

Now lets reduce the middle string:

11101010001000100
1101010001000100
111010001000100  
11010001000100
1010001000100
1010001000100
101000100010
10100100010
1010100010
10101010
1010100
101100
10100
1010
100
10
0 

Hence the s would become: 00 0 11111

There 2 leading 0s and 5 trailing 1s with the reduced 10 substring's 0 in the middle is the final answer.
 
'''


def solve(n, s):

    # check if there exists at least one occurrence of 10
    is_present_10 = False
    for i in xrange(1, n):

        if s[i-1] > s[i]:
            is_present_10 = True
            break

    if not is_present_10:
        return s

    # find the count of 0s till the first 1
    i = 0
    while i < n and s[i] == '0':
        i += 1

    leading_zeroes = i

    # find eh count of 1s till the first 0 from the back
    i = n-1
    while i >= 0 and s[i] == '1':
        i -= 1

    trailing_ones = n - i - 1

    return ('0' * leading_zeroes) + '0' + ('1' * trailing_ones)


if __name__ == "__main__":

    '''
    1
    4
    0101
    '''
    t = int(raw_input())

    results = list()
    for _ in xrange(0, t):
        n = int(raw_input())
        s = raw_input()
        results.append(solve(n, s))

    for result in results:
        print result
