You are given a binary string S of length N. You can perform the following operation on it:
Pick any non-empty even-length [subsequence] of the string.
Suppose the subsequence has length 2k. Then, move the first k characters to the beginning of S and the other k to the end of S (without changing their order).

For example, suppose S = 01100101110. Here are some moves you can make (the chosen subsequence is marked in red):
0\textcolor{red}{1}10\textcolor{red}{0}101110 \to \textcolor{red}{1}010101110\textcolor{red}{0}
01\textcolor{red}{10}01\textcolor{red}{0}1\textcolor{red}{1}10 \to \textcolor{red}{10}0101110\textcolor{red}{01}
011\textcolor{red}{00101110} \to \textcolor{red}{0010}011\textcolor{red}{1110}

What is the lexicographically smallest string that can be obtained after performing this operation several (possibly, zero) times?

Note: A binary string A is said to be lexicographically smaller than another binary string B of the same length if there exists an index i such that:
A_{1} = B_{1}, A_{2} = B_{2}, \ldots, A_{i-1} = B_{i-1}
A_{i} = 0 and B_{i} = 1.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases. The description of the test cases follows.
- Each test case consists of two lines of input.
- The first line of each test case contains a single integer N, the length of string S.
- The second line contains a binary string of length N.

------ Output Format ------ 

For each testcase, output a single line containing the lexicographically shortest binary string that can be obtained by performing the given operation several times.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 2\cdot 10^{5}$
$S$ is a binary string, i.e, contains only the characters $0$ and $1$.
- The sum of $N$ across all test cases won't exceed $2\cdot 10^{5}$.

----- Sample Input 1 ------ 
4
2
10
4
1001
5
11111
7
0010100

----- Sample Output 1 ------ 
10
0011
11111
0000011

----- explanation 1 ------ 
Test case $1$: There's only one move possible, and it gives back the original string when made. So, $S$ cannot be changed, and the answer is $10$.

Test case $2$: Make the following moves:
- $1\textcolor{red}{0}0\textcolor{red}{1} \to \textcolor{red}{0}10\textcolor{red}{1}$
- $\textcolor{red}{01}01 \to \textcolor{red}{0}01\textcolor{red}{1}$

This is the lexicographically smallest string.

Test case $3$: Performing any move doesn't change the string.

Test case $4$: Make the move $\textcolor{red}{001}0\textcolor{red}{1}00 \to \textcolor{red}{00}000\textcolor{red}{11}$.

Difficulty: EASY
Tags: Sorting
Skill types: Sorting

Starter code:

Solutions:
p = int(input())
for i in range(p):
	q = int(input())
	s = input()
	if q <= 2:
		print(s)
	else:
		a = ''
		b = ''
		for i in range(q):
			if s[i] == '1':
				a += '1'
			else:
				b += '0'
		print(b + a)


for _ in range(int(input())):
	n = int(input())
	l = input()
	a = l.count('0')
	d = n - a
	if n < 3:
		print(l)
	else:
		print('0' * a + '1' * d)


for i in range(int(input())):
	n = int(input())
	s = input()
	if len(s) <= 2:
		print(s)
	else:
		print(''.join(sorted(s)))


for _ in range(int(input())):
	n = int(input())
	s = input()
	zeros = s.count('0')
	ones = n - zeros
	if zeros == 1 and s[-1] == '0' and (n == 2):
		print(s)
	else:
		for i in range(zeros):
			print(0, end='')
		for i in range(ones):
			print(1, end='')
		print()


for i in range(int(input())):
	n = int(input())
	s = input()
	if n < 3:
		print(s)
	else:
		l = list(s)
		(c, d) = (l.count('0'), l.count('1'))
		for j in range(c):
			print(0, end='')
		for j in range(0, d):
			print(1, end='')
		print()


for _ in range(int(input())):
	n = int(input())
	s = input()
	if n <= 2:
		print(s)
	else:
		print(''.join(sorted(s)))


for i in range(int(input())):
	n = int(input())
	s = input()
	c = 0
	d = 0
	if s == '10':
		print('10')
	else:
		for i in s:
			if i == '0':
				c += 1
			else:
				d += 1
		print(c * '0' + d * '1')


for _ in range(int(input())):
	n = int(input())
	s = input()
	z = s.count('0')
	o = s.count('1')
	if z <= 1 and o <= 1:
		print(s)
	else:
		print('0' * z + '1' * o)


cases = int(input())
for _ in range(cases):
	n = int(input())
	binary = input()
	s = list(binary)
	s.sort()
	if len(s) > 2:
		print(''.join(s))
	else:
		print(binary)


for _ in range(int(input())):
	n = int(input())
	s = input()
	if n <= 2:
		print(s)
		continue
	(c0, c1) = (s.count('0'), s.count('1'))
	print('0' * c0 + '1' * c1)


t = int(input())
while t:
	count = 0
	n = int(input())
	s = input()
	l = []
	if n > 2:
		for i in s:
			if i == '0':
				print(i, end='')
			else:
				count = count + 1
		for i in range(count):
			print(1, end='')
		print()
	else:
		print(s)
	t = t - 1


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	ans = ''
	c0 = 0
	c1 = 0
	if n < 3:
		print(s)
	else:
		for j in range(n):
			if s[j] == '0':
				c0 += 1
			else:
				c1 += 1
		ans += '0' * c0 + '1' * c1
		print(ans)


for _ in range(int(input())):
	(n, s) = (int(input()), list(map(str, input())))
	print(''.join(sorted(s)) if n != 2 else ''.join(s))


for _ in range(int(input())):
	n = int(input())
	s = list(map(str, input()))
	if s == ['1', '0']:
		print(10)
	else:
		s.sort()
		print(''.join(s))


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	flag = True
	if n == 1 or n == 2:
		flag = False
		print(s)
	else:
		for i in range(1, n - 1):
			if s[i] == 0:
				flag = False
				print(s)
				break
	p = ''
	if flag == True:
		p += '0' * s.count('0') + '1' * s.count('1')
		print(p)


t = int(input())
while t > 0:
	n = int(input())
	s = input()
	str1 = ''
	str2 = ''
	if n <= 2:
		print(s)
	else:
		for i in range(n):
			if s[i] == '0':
				str1 += s[i]
			else:
				str2 += s[i]
		print(str1 + str2)
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	a = input()
	if n <= 2:
		print(a)
	else:
		a = sorted(a)
		for i in a:
			print(i, end='')
		print()


n = int(input())
for i in range(n):
	y = int(input())
	z = input()
	if y <= 2:
		print(z)
	else:
		a = ''
		b = ''
		for i in range(y):
			if z[i] == '1':
				a += '1'
			else:
				b += '0'
		print(b + a)


for _ in range(int(input())):
	n = int(input())
	l = input()
	p = sorted([*l])
	m = ''.join(p)
	if n > 2:
		print(m)
	else:
		print(l)


for i in range(int(input())):
	x = int(input())
	s = input()
	if x <= 2:
		print(s)
	else:
		v = ''
		p = ''
		for i in range(len(s)):
			if s[i] == '1':
				v += '1'
			else:
				p += '0'
		print(p + v)


for _ in range(int(input())):
	n = int(input())
	str1 = str(input())
	str2 = ''
	c = 0
	if len(str1) == 2:
		str2 = str1
	else:
		for i in range(n):
			if str1[i] == '1':
				c += 1
		for i in range(n - c):
			str2 += '0'
		for i in range(c):
			str2 += '1'
	print(str2)


for i in range(int(input())):
	n = int(input())
	s = input()
	if s == '10':
		print(s)
	else:
		print(''.join(sorted(s)))


t = int(input())
for i in range(t):
	n = int(input())
	k = input()
	if len(k) == 2:
		print(k)
	else:
		a = []
		for i in range(len(k)):
			a.append(k[i])
		a.sort()
		s = ''
		for i in a:
			s += i
		print(s)


for i in range(int(input())):
	n = int(input())
	l = input()
	if len(l) <= 2:
		print(l)
	else:
		l = list(l)
		p = l.count('1')
		t = ''
		for i in range(0, n - p):
			t += '0'
		for j in range(n - p, n):
			t += '1'
		print(t)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	if len(s) == 2:
		print(s)
	else:
		a = ''
		b = ''
		for i in range(n):
			if s[i] == '1':
				a += '1'
			else:
				b += '0'
		print(b + a)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	if n > 2:
		l = []
		for i in range(n):
			l.append(s[i])
		l.sort()
		p = ''.join(l)
		print(p)
	else:
		print(s)


t = int(input())
for i in range(1, t + 1):
	a = int(input())
	s = input()[:a]
	(count_0, count_1) = (s.count('0'), s.count('1'))
	if count_0 == count_1 == 1:
		print(s)
	else:
		print('0' * count_0 + '1' * count_1)


for _ in range(int(input())):
	l = int(input())
	s = str(input())
	c = 0
	str1 = ''
	if len(s) == 2:
		str1 = s
	else:
		for i in range(l):
			if s[i] == '1':
				c += 1
		str1 = str1 + '0' * (l - c) + '1' * c
	print(str1)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	if len(s) > 2:
		k = sorted(s)
		r = ''
		for i in k:
			r += i
		print(r)
	else:
		print(s)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	if len(s) <= 2:
		print(s)
	else:
		a = sorted(s)
		a1 = ''.join(a)
		print(a1)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	if len(s) <= 2:
		print(s)
	else:
		a = sorted(s)
		a = ''.join(a)
		print(a)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	if s == '10':
		print('10')
	elif s == '01':
		print('01')
	else:
		s1 = ''
		x = s.count('0')
		y = s.count('1')
		for i in range(x):
			s1 = s1 + '0'
		for i in range(y):
			s1 = s1 + '1'
		print(s1)


for i in range(int(input())):
	b = int(input())
	p = input()
	if p == '10':
		print(p)
	else:
		print(''.join(sorted(p)))


num = int(input())
for i in range(num):
	x = int(input())
	s = input()
	if len(s) > 2:
		c1 = 0
		l = list(s)
		p = l.count('1')
		str1 = ''
		k = 0
		while k < len(s):
			if k < len(s) - p:
				str1 = str1 + '0'
			else:
				str1 = str1 + '1'
			k = k + 1
		print(str1)
	else:
		print(s)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	if n <= 2:
		print(s)
	else:
		one = s.count('1')
		zero = s.count('0')
		res = '0' * zero + '1' * one
		print(res)


t = int(input())
for i in range(t):
	n = int(input())
	s = str(input())
	c = 0
	c1 = 0
	if n <= 2:
		print(s)
	else:
		for j in s:
			if j == '0':
				c += 1
			elif j == '1':
				c1 += 1
		s1 = '0' * c
		s2 = '1' * c1
		print(s1 + s2)


t = int(input())
while t > 0:
	n = int(input())
	s = input()
	if n == 2:
		print(s)
	else:
		zer = 0
		one = 0
		for i in s:
			if '0' in i:
				zer += 1
			else:
				one += 1
		print('0' * zer + '1' * one)
	t = t - 1


for i in range(int(input())):
	n = int(input())
	str1 = input()
	list1 = list(str1)
	if len(list1) == 2:
		print(str1)
	else:
		list1.sort()
		str2 = ''
		for i in list1:
			str2 += i
		print(str2)


t = int(input())
while t > 0:
	n = int(input())
	s = input()
	if len(s) == 2:
		print(s)
	else:
		s = list(s)
		for i in s:
			i = int(i)
		s.sort()
		a = ''
		for i in s:
			a = a + i
		print(a)
	t = t - 1


T = int(input())
for i in range(T):
	n = int(input())
	bs = input()
	if len(bs) == 2:
		print(bs)
	else:
		a = bs.count('0')
		b = bs.count('1')
		ans = '0' * a + '1' * b
		print(ans)


q = int(input())
while q > 0:
	n = int(input())
	s = input()
	if n <= 2:
		print(s)
	else:
		s = list(s)
		c = 0
		for i in s:
			if i == '0':
				c += 1
		for i in range(0, c):
			s[i] = '0'
		for i in range(c, len(s)):
			s[i] = '1'
		x = ''
		for i in s:
			x = x + i
		print(x)
	q = q - 1


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	if n == 2:
		print(s)
	else:
		c1 = s.count('1')
		c2 = s.count('0')
		string = ''
		l1 = [1] * c1
		l0 = [0] * c2
		l = l0 + l1
		for i in l:
			string = string + str(i)
		print(string)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	if n < 3:
		print(s)
	else:
		s = ''.join(sorted(s))
		print(s)


t = int(input())
for i in range(0, t):
	n = int(input())
	s = input()
	if n == 2 or n == 1:
		print(s)
	else:
		n1 = s.count('0')
		n2 = s.count('1')
		print('0' * n1 + '1' * n2)


n = int(input())
for i in range(n):
	t = int(input())
	word = input()
	if len(word) == 2:
		print(word)
	else:
		d = {}
		for i in word:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		if '0' in d:
			word = '0' * d['0']
			if '1' in d:
				word += '1' * d['1']
		elif '1' in d:
			word = '1' * d['1']
		print(word)


for _ in range(int(input())):
	n = int(input())
	s = input()
	if len(s) < 3:
		print(s)
	else:
		x = ''.join(sorted(s))
		print(x)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	co = s.count('1')
	if n < 3:
		print(s)
		continue
	for i in range(n - co):
		print(0, end='')
	for i in range(co):
		print(1, end='')
	print(' ')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	s1 = list(s)
	s1.sort()
	if len(s1) > 2:
		print(''.join(s1))
	else:
		print(s)


t = int(input())
for ni in range(t):
	n = int(input())
	s = input()
	if n == 2:
		print(s)
	else:
		print('0' * s.count('0') + '1' * s.count('1'))