Chef is given a binary string A of length N. He can perform the following operation on A any number of times:
Choose L and R (1 ≤ L ≤ R ≤ N), such that, in the [substring] A[L,R], the number of 1s is equal to the number of 0s and reverse the substring A[L,R].

Find the lexicographically smallest string that Chef can obtain after performing the above operation any (possibly zero) number of times on A.

String X is lexicographically smaller than string Y, if either of the following satisfies:
X is a prefix of Y and X \neq Y.
There exists an index i such that X_{i} < Y_{i} and X_{j} = Y_{j}, \forall j such that 1 ≤ j < i.

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

- First line will contain T, the number of test cases. Then the test cases follow. Each test case contains two lines.
- The first line contains the integer N, the length of the binary string.
- The second line contains the binary string A.

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

For each test case, print the lexicographically smallest binary string that can be obtained after performing the operation any (possibly zero) number of times.

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

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{5}$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
2
5
01100
4
0000

----- Sample Output 1 ------ 
00011
0000
----- explanation 1 ------ 
Test Case $1$: Chef can choose $L = 2$ and $R=5$. The chosen substring, $A[2,5] = 1100$. On reversing this, we get $0011$. Thus, the final string is $A = 00011$.  Note that this is the lexicographically smallest string possible.

Test Case $2$: Since the string is already lexicographically minimum, Chef does not need to apply any operation.

Source: codechef | Difficulty: EASY
Tags: String algorithms

Sorting

Data structures


Solutions:
goals = int(input())
for distractions in range(goals):
	wife = int(input())
	life = input()
	print(*sorted(life), sep='')


for i in range(int(input())):
	N = int(input())
	s = input()
	print(*sorted(s), sep='')


for _ in range(int(input())):
	n = int(input())
	s = input()
	s1 = sorted(s)
	str = ''
	for i in s1:
		str = str + i
	print(str)


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


for i in range(int(input())):
	n = int(input())
	p = list(input())
	p.sort()
	print(*p, sep='')


for i in range(int(input())):
	n = int(input())
	a = input()
	print('0' * a.count('0') + '1' * a.count('1'))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(input())
	a.sort()
	s = ''
	for i in a:
		s = s + i
	print(s)


for _ in range(int(input())):
	n = int(input())
	l = input()
	print(''.join(sorted(l)))


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


n = int(input())
for i in range(n):
	s = int(input())
	m = list(input())
	m.sort()
	print(''.join(m))


t = int(input())
for _ in range(t):
	n = int(input())
	s = list(input())
	s.sort()
	print(''.join(s))


for testcase in range(int(input())):
	n = int(input())
	s = input()
	print(''.join(sorted(s)))


t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	print(''.join(sorted(a)))


T = int(input())
for t in range(T):
	N = int(input())
	A = list(input())
	A = [int(a) for a in A]
	A.sort()
	A = ''.join([str(a) for a in A])
	print(A)


for t in range(int(input())):
	n = int(input())
	arr = list(input())
	arr_s = sorted(arr)
	result = ''.join((str(a) for a in arr_s))
	print(result)


for i in range(int(input())):
	N = int(input())
	Str = input()
	count = Str.count('0')
	ans = '0' * count + '1' * (N - count)
	print(ans)


t = int(input())
for test in range(0, t):
	size = int(input())
	string = input()
	one = ''
	zero = ''
	for i in string:
		if i == '1':
			one += i
		else:
			zero += i
	print(zero + one)


for i in range(int(input())):
	n = int(input())
	string = sorted([i for i in input()])
	print(*string, sep='')


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


for i in range(int(input())):
	n = int(input())
	c = ''
	s = input()
	l = sorted(list(s))
	for i in l:
		c += i
	print(c)


for i in range(int(input())):
	x = int(input())
	y = input()
	y1 = y.count('1')
	new = ''
	for i in range(x - y1):
		new += '0'
	for i in range(y1):
		new += '1'
	print(new)


for _ in range(int(input())):
	n = int(input())
	y = input()
	print(''.join(sorted(y)))


t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	ans = []
	for i in a:
		ans.append(i)
	ans.sort()
	for j in range(len(ans)):
		print(ans[j], end='')
	print()


n = int(input())
for i in range(0, n):
	m = int(input())
	s = input()
	g = len(s)
	o = s.count('0')
	print(o * '0' + (g - o) * '1')


for _ in range(int(input())):
	n = int(input())
	s = input()
	zeros = s.count('0')
	ones = s.count('1')
	ans = '0' * zeros + '1' * ones
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	list = []
	str = ''
	s = input()
	for i in s:
		list.append(i)
	list.sort()
	for each in list:
		str = str + each
	print(str)


for i in range(int(input())):
	n = int(input())
	s = input()
	print('0' * s.count('0') + '1' * s.count('1'))


cases = int(input())
for _ in range(cases):
	n = int(input())
	s = input()
	zeroes = s.count('0')
	ones = s.count('1')
	res = '0' * zeroes + '1' * ones
	print(res)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	lst = list(s)
	lst.sort()
	print(*lst, sep='')


for _ in range(int(input())):
	n = int(input())
	a = sorted([i for i in input()])
	print(*a, sep='')


for i in range(int(input())):
	x = int(input())
	s = input()
	a = s.count('0')
	b = s.count('1')
	print(a * '0' + b * '1')


t = int(input())
for tc in range(t):
	n = int(input())
	s = input()
	r = ''
	p = ''
	for j in s:
		if j == '0':
			r += j
		else:
			p += j
	print(r + p)


t = int(input())
for i in range(t):
	s = int(input())
	a = input()
	l = []
	for i in a:
		l.append(int(i))
	l.sort()
	print(*l, sep='')


for _ in range(int(input())):
	n = int(input())
	a = input()
	a = sorted(a)
	print(''.join(a))


for _ in range(int(input())):
	x = int(input())
	y = [int(x) for x in input()]
	y.sort()
	a = ''
	for i in range(x):
		a = a + str(y[i])
	print(a)


T = int(input())
for i in range(T):
	N = int(input())
	S = input()
	P = S.count('0')
	M = S.count('1')
	S1 = sorted(S)
	if len(set(S1)) == 1:
		print(S)
	else:
		print(''.join(S1))


test_cases = int(input())
for i in range(test_cases):
	n = int(input())
	binary = input()
	res = ''.join(sorted(binary))
	print(res)


test = int(input())
for i in range(test):
	x = int(input())
	n = input()
	print(''.join(sorted(n)))


for _ in range(int(input())):
	l = int(input())
	s = input()
	k = sorted(s)
	print(''.join(k))


u = int(input())
for _ in range(u):
	q = int(input())
	b = input()
	print(''.join(sorted(b)))


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


for _ in range(int(input())):
	x = int(input())
	s = input()
	print(''.join(sorted(s)))


for _ in range(int(input())):
	n = int(input())
	l1 = input()
	print(''.join(sorted(l1)))


for i in range(int(input())):
	n = int(input())
	s1 = input()
	c = s1.count('0')
	print('0' * c + '1' * (n - c))


for tc in range(int(input())):
	n = int(input())
	a = input()
	z = a.count('0')
	ans = '0' * z + '1' * (n - z)
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	print(''.join(map(str, sorted(s))))


t = int(input())
while t > 0:
	o = ''
	l = int(input())
	s = input()
	k = s.count('1')
	for i in range(l - k):
		o += '0'
	for j in range(k):
		o += '1'
	print(o)
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	x = 0
	for i in s:
		if i == '0':
			x += 1
	s1 = '0' * x + '1' * (n - x)
	print(s1)


n = int(input())
for i in range(n):
	x = int(input())
	st1 = input()
	c = st1.count('1')
	l = len(st1) - c
	str1 = l * '0' + c * '1'
	print(str1)


t = int(input())
for _ in range(t):
	l = int(input())
	s = input()
	print(''.join(sorted(s)))