Alice and Bob are playing a game with a binary string S of length N and an empty string T.  
They both take turns and Alice plays first.

In Alice's turn, she picks the first character of string S, appends the character to either the front or back of string T and deletes the chosen character from string S.
In Bob's turn, he picks the last character of string S, appends the character to either the front or back of string T and deletes the chosen character from string S.

The game stops when S becomes empty.  
Alice wants the resultant string T to be lexicographically smallest, while Bob wants the resultant string T to be lexicographically largest possible.

Find the resultant string T, if both of them play optimally.

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

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

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

For each test case, print the the resultant string T, if both of them play optimally.

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

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 1000$
$S$ can only contain the characters $0$ or $1$.

----- Sample Input 1 ------ 
4
2
10
4
0001
6
010111
10
1110000010
----- Sample Output 1 ------ 
10
0100
101101
0011011000
----- explanation 1 ------ 
Test case $1$: Alice picks the first bit which is $1$ and appends it to the empty string $T$. Bob then picks the last bit $0$ and appends it to the back of $T$ making the resultant string to be $10$.

Test case $2$:
- Alice picks $0$ and adds it to $T$. Thus, $S$ becomes $001$ and $T$ becomes $0$.
- Bob picks $1$ and adds it to front of $T$. Thus, $S$ becomes $00$ and $T$ becomes $10$.
- Alice picks $0$ and adds it to front of $T$. Thus, $S$ becomes $0$ and $T$ becomes $010$.
- Bob picks $0$ and adds it to back of $T$. Thus, $S$ becomes empty and $T$ becomes $0100$.

Source: codechef | Difficulty: EASY
Tags: Data structures


Solutions:
for _ in range(int(input())):
	n = int(input())
	s = input()
	l = 0
	m = 1
	a = []
	for i in range(n):
		if i % 2 == 0:
			if s[l] == '0':
				a.insert(0, '0')
			else:
				a.append('1')
			l += 1
		else:
			if s[-l] == '1':
				a.insert(0, '1')
			else:
				a.append('0')
			m += 1
	b = ''.join(a)
	print(b)


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


from collections import Counter

def test():
	n = int(input())
	s = input()
	l = 0
	m = 1
	a = []
	for i in range(n):
		if i % 2 == 0:
			if s[l] == '0':
				a.insert(0, '0')
			else:
				a.append('1')
			l += 1
		else:
			if s[-l] == '1':
				a.insert(0, '1')
			else:
				a.append('0')
			m += 1
	b = ''.join(a)
	print(b)
t = int(input())
for _ in range(t):
	test()


t = int(input())
for i in range(t):
	n = int(input())
	s = list(input())
	(T, turn) = ('', 1)
	while len(s) != 0:
		if turn % 2 == 1:
			if s[0] == '0':
				T = s[0] + T
			else:
				T = T + s[0]
			(s, turn) = (s[1:], turn + 1)
		else:
			if s[-1] == '1':
				T = s[-1] + T
			else:
				T = T + s[-1]
			(s, turn) = (s[:-1], turn + 1)
	print(T)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	l = 0
	a = []
	for i in range(n):
		if i % 2 == 0:
			if s[l] == '0':
				a.insert(0, '0')
			else:
				a.append('1')
			l += 1
		elif s[-l] == '1':
			a.insert(0, '1')
		else:
			a.append('0')
	b = ''.join(a)
	print(b)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	m = []
	l = 0
	k = 1
	for i in range(n):
		if i % 2 == 0:
			if s[l] == '0':
				m.insert(0, '0')
			else:
				m.append('1')
			l = l + 1
		else:
			if s[-k] == '1':
				m.insert(0, '1')
			else:
				m.append('0')
			k = k + 1
	print(''.join(m))


from collections import deque
T = int(input())
for t in range(T):
	n = int(input())
	s = input()
	q = deque()
	sd = deque(list(s))
	alice = True
	while len(sd) > 0:
		if alice:
			current = sd.popleft()
			if current == '0':
				q.appendleft(current)
			else:
				q.append(current)
		else:
			current = sd.pop()
			if current == '0':
				q.append(current)
			else:
				q.appendleft(current)
		alice = not alice
	print(''.join(q))


for _ in range(int(input())):
	N = int(input())
	S = input()
	T = S[0]
	if N % 2 == 0:
		median = int(N / 2)
	else:
		median = int(N / 2) + 1
	for i in range(1, median):
		if S[N - i] == '0':
			T = T + '0'
		else:
			T = '1' + T
		if S[i] == '0':
			T = '0' + T
		else:
			T = T + '1'
	if N % 2 == 0:
		if S[median] == '0':
			T = T + '0'
		else:
			T = '1' + T
	print(T)


t = int(input())
for tc in range(t):
	n = int(input())
	s = input()
	m = []
	x = 0
	y = 1
	for j in range(n):
		if j % 2 == 0:
			if s[x] == '0':
				m.insert(0, '0')
			else:
				m.append('1')
			x += 1
		else:
			if s[-x] == '1':
				m.insert(0, '1')
			else:
				m.append('0')
			y += 1
	p = ''.join(m)
	print(p)


banyak_kasus = int(input())

def TambahDepan(huruf, tulisan):
	return tulisan.join([huruf, tulisan])[:len(tulisan) + 1]
while banyak_kasus > 0:
	banyak_karakter = int(input())
	biner_s = input()
	biner_s1 = biner_s[1:banyak_karakter]
	resultan = biner_s[0]
	(c, n, m) = (0, 0, banyak_karakter - 2)
	for x in range(len(biner_s1)):
		if c % 2 == 0:
			if biner_s1[m] == '0':
				resultan += biner_s1[m]
			else:
				resultan = TambahDepan(biner_s1[m], resultan)
			m -= 1
		else:
			if biner_s1[n] == '1':
				resultan += biner_s1[n]
			else:
				resultan = TambahDepan(biner_s1[n], resultan)
			n += 1
		c += 1
	print(resultan)
	banyak_kasus -= 1


for i in range(int(input())):
	n = int(input())
	st = input()
	ls = []
	(l, k) = (0, -1)
	for i in range(n):
		if i % 2 == 0:
			if st[l] == '0':
				ls.insert(0, '0')
			else:
				ls.append('1')
			l += 1
		else:
			if st[k] == '1':
				ls.insert(0, '1')
			else:
				ls.append('0')
			k -= 1
	print(''.join((x for x in ls)))


x = int(input())
for i in range(0, x):
	length = int(input())
	string = input()
	suspense = ''
	alice = 0
	bob = length - 1
	while alice <= bob:
		if string[alice] == '0':
			suspense = string[alice] + suspense
		else:
			suspense = suspense + string[alice]
		if alice < bob:
			if string[bob] == '0':
				suspense = suspense + string[bob]
			else:
				suspense = string[bob] + suspense
			bob += -1
		alice += 1
	print(suspense)


for _ in range(int(input())):
	n = int(input())
	s = list(input())
	t = []
	turn = 1
	while s != []:
		if turn % 2 != 0:
			c = s[0]
			if c == '0':
				t.insert(0, 0)
			else:
				t.append(1)
			v = s.pop(0)
		else:
			c = s[n - 1]
			if c == '0':
				t.append(0)
			else:
				t.insert(0, 1)
			v = s.pop(n - 1)
		turn += 1
		n -= 1
	print(*t, sep='')


tc = int(input())
for _ in range(tc):
	n = int(input())
	s = list(input())
	t = ''
	for i in range(0, n // 2):
		if s[i] == '0':
			t = s[i] + t
		else:
			t = t + s[i]
		if s[n - 1 - i] == '0':
			t = t + s[n - 1 - i]
		else:
			t = s[n - 1 - i] + t
	if n % 2 == 1:
		if s[n // 2] == '0':
			t = s[n // 2] + t
		else:
			t = t + s[n // 2]
	print(t)


t = int(input())
while t:
	t -= 1
	n = int(input())
	s = input()
	ans = ''
	alice_turn = 1
	a = 0
	b = n - 1
	while b >= a:
		if alice_turn:
			alice_turn = 0
			if s[a] == '1':
				ans = ans + '1'
			elif s[a] == '0':
				ans = '0' + ans
			a += 1
		else:
			alice_turn = 1
			if s[b] == '1':
				ans = '1' + ans
			elif s[b] == '0':
				ans = ans + '0'
			b -= 1
	print(ans)


for k in range(int(input())):
	n = int(input())
	s = list(input())
	v = ''
	for i in range(n):
		if i % 2:
			(a, s) = (s[-1], s[:-1])
			if a == '0':
				v += a
			else:
				v = a + v
		else:
			(a, s) = (s[0], s[1:])
			if a == '0':
				v = a + v
			else:
				v += a
	print(v)


for i in range(int(input())):
	n = int(input())
	s1 = input()
	s = ''
	for i in range(len(s1)):
		if n - i - 1 <= i:
			break
		else:
			if s1[i] == '0':
				s = '0' + s
			else:
				s = s + '1'
			if s1[n - i - 1] == '0':
				s = s + '0'
			else:
				s = '1' + s
	if len(s1) % 2 != 0:
		if s1[n // 2] == '0':
			s = '0' + s
		else:
			s = s + '1'
	print(s)


for _ in range(int(input())):
	num = int(input())
	string = input()
	s_list = list(string)
	result = []
	while s_list:
		a = s_list.pop(0)
		if int(a) == 1:
			result.append(a)
		else:
			result.insert(0, a)
		if s_list:
			b = s_list.pop(-1)
			if int(b) == 1:
				result.insert(0, b)
			else:
				result.append(b)
	print(''.join(result))


te = int(input())
for _ in range(te):
	n = int(input())
	s = input()
	t = []
	m = 0
	for i in range(n):
		if i % 2 != 0:
			if s[-m] == '1':
				t.insert(0, '1')
			else:
				t.append('0')
		else:
			if s[m] == '0':
				t.insert(0, '0')
			else:
				t.append('1')
			m += 1
	b = ''.join(t)
	print(b)


for tc in range(int(input())):
	n = int(input())
	s = input()
	t = ''
	(l, r) = (0, n - 1)
	while l < r:
		leftele = s[l]
		rightele = s[r]
		if leftele == '0':
			t = '0' + t
		else:
			t = t + '1'
		if rightele == '0':
			t = t + '0'
		else:
			t = '1' + t
		l += 1
		r -= 1
	if l == r:
		leftele = s[l]
		if leftele == '0':
			t = '0' + t
		else:
			t = t + '1'
	print(t)


for _ in range(int(input())):
	n = int(input())
	l = input()
	t = []
	for i in range(0, n // 2):
		if l[i] == '0':
			t.insert(0, l[i])
		else:
			t.insert(len(t), l[i])
		if l[-i - 1] == '1':
			t.insert(0, l[-i - 1])
		else:
			t.insert(len(t), l[-i - 1])
	if n % 2 != 0:
		if l[n // 2] == '0':
			t.insert(0, l[n // 2])
		else:
			t.insert(len(t), l[n // 2])
	print(''.join(t))


def solve():
	n = int(input())
	s = input()
	ans = ''
	for i in range(n // 2):
		if int(s[i]):
			ans = ans + s[i]
		else:
			ans = s[i] + ans
		if int(s[n - i - 1]):
			ans = s[n - i - 1] + ans
		else:
			ans = ans + s[n - i - 1]
	if n % 2:
		if int(s[n // 2]):
			ans = ans + s[n // 2]
		else:
			ans = s[n // 2] + ans
	print(ans)
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = ''
	(pntr1, pntr2) = (0, n - 1)
	flg = False
	while pntr1 <= pntr2:
		if flg:
			if s[pntr2] == '0':
				ans += s[pntr2]
			else:
				ans = s[pntr2] + ans
			pntr2 -= 1
		else:
			if s[pntr1] == '0':
				ans = s[pntr1] + ans
			else:
				ans += s[pntr1]
			pntr1 += 1
		flg = not flg
	print(ans)


def main():
	for _ in range(int(input())):
		N = int(input())
		S = input()[:N]
		T = []
		l = 0
		for i in range(N):
			if i % 2 == 0:
				if S[l] == '0':
					T.insert(0, '0')
				else:
					T.append('1')
				l += 1
			elif S[-l] == '1':
				T.insert(0, '1')
			else:
				T.append('0')
		print(''.join(T))
main()


for i in range(int(input())):
	a = int(input())
	b = input()
	b = list(b)
	c = ''
	while len(b) != 0:
		if b[0] == '0':
			c = '0' + c
		else:
			c += '1'
		b.remove(b[0])
		if len(b) == 0:
			break
		if b[-1] == '1':
			c = '1' + c
		else:
			c += '0'
		b.pop(-1)
	print(c)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	f = []
	l = 0
	for i in range(n):
		if i % 2 == 0:
			if s[l] == '0':
				f.insert(0, '0')
			else:
				f.append('1')
			l += 1
		elif s[-l] == '1':
			f.insert(0, '1')
		else:
			f.append('0')
	print(''.join(f))


def sus(s, n):
	t = ''
	i = 0
	j = 0
	while len(s) != 0:
		if j % 2 == 0:
			if s[i] == '0':
				t = '0' + t
				s = s[:i] + s[i + 1:]
			else:
				t = t + '1'
				s = s[:i] + s[i + 1:]
		elif s[-1] == '1':
			t = '1' + t
			s = s[:-1]
		else:
			t = t + '0'
			s = s[:-1]
		j += 1
	return t
for _ in range(int(input())):
	n = int(input())
	s = input()
	print(sus(s, n))


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	A = []
	B = []
	for j in s:
		A.append(j)
	k = 0
	while len(A) != 0:
		if k % 2 == 0:
			if A[0] == '0':
				B.insert(0, '0')
			else:
				B.append('1')
			A.remove(A[0])
		else:
			if A[len(A) - 1] == '0':
				B.append('0')
			else:
				B.insert(0, '1')
			A = A[:len(A) - 1]
		k += 1
	a = ''
	for j in B:
		a += str(j)
	print(a)


for _ in range(int(input())):
	n = int(input())
	s = input()
	t = ''
	if n % 2 == 0:
		s1 = s[0:n // 2]
		s2 = s[n // 2:n]
		for i in range(n // 2):
			if s1[i] == '0':
				t = '0' + t
			elif s1[i] == '1':
				t = t + '1'
			if i == n // 2:
				break
			if s2[len(s2) - 1 - i] == '0':
				t = t + '0'
			elif s2[len(s2) - 1 - i] == '1':
				t = '1' + t
	else:
		s1 = s[0:n // 2 + 1]
		s2 = s[n // 2 + 1:n]
		for i in range(n // 2 + 1):
			if s1[i] == '0':
				t = '0' + t
			elif s1[i] == '1':
				t = t + '1'
			if i == n // 2:
				break
			if s2[len(s2) - 1 - i] == '0':
				t = t + '0'
			elif s2[len(s2) - 1 - i] == '1':
				t = '1' + t
	print(t)


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	ans = ''
	i = 0
	j = n - 1
	while i < j:
		if i < n // 2:
			a = ans + s[i]
			b = s[i] + ans
			if int(a, 2) > int(b, 2):
				ans = b
			else:
				ans = a
		if j >= n // 2:
			a = ans + s[j]
			b = s[j] + ans
			if int(a, 2) > int(b, 2):
				ans = a
			else:
				ans = b
		i = i + 1
		j = j - 1
	if i == j and n % 2 != 0:
		a = ans + s[i]
		b = s[i] + ans
		if int(a, 2) > int(b, 2):
			ans = b
		else:
			ans = a
	print(ans)


t = int(input())
while t > 0:
	n = int(input())
	List = input()
	List_Ans = list()
	for k in range(0, n):
		if k % 2 == 0:
			List_Ans.insert(0, '0') if List[int(k / 2)] == '0' else List_Ans.append('1')
		else:
			List_Ans.insert(0, '1') if List[n - int((k + 1) / 2)] == '1' else List_Ans.append('0')
	for i in List_Ans:
		print(i, end='')
	print()
	t = t - 1


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	s = list(s)
	t = ''
	j = 0
	while n > 0:
		n -= 1
		if j % 2 == 0:
			j += 1
			x = s.pop(0)
			if x == '1':
				t += '1'
			else:
				t = '0' + t
		else:
			j += 1
			x = s.pop(-1)
			if x == '0':
				t += '0'
			else:
				t = '1' + t
	print(t)


for i in range(int(input())):
	n = int(input())
	s = input()
	ia = -1
	ib = n
	T = ''
	while True:
		ia += 1
		if ia >= ib:
			break
		if s[ia] == '0':
			T = '0' + T
		else:
			T += '1'
		ib -= 1
		if ib <= ia:
			break
		if s[ib] == '0':
			T += '0'
		else:
			T = '1' + T
	print(T)


for _ in range(int(input())):
	n = int(input())
	s = list(input().strip())
	l = s[::-1]
	t = []
	for i in range(n // 2):
		if s[i] == '0':
			t.insert(0, s[i])
		else:
			t.append(s[i])
		if l[i] == '0':
			t.append(l[i])
		else:
			t.insert(0, l[i])
	if n % 2 == 1:
		if s[n // 2] == '0':
			t.insert(0, s[n // 2])
		else:
			t.append(s[n // 2])
	print(''.join(t))


for _ in range(int(input())):
	N = int(input())
	S = list(input())
	i = 0
	T = ''
	while i < len(S):
		if len(T) == len(S):
			break
		if int(T + S[i]) < int(S[i] + T):
			T += S[i]
		else:
			T = S[i] + T
		if len(T) == len(S):
			break
		if int(T + S[-(i + 1)]) > int(S[-(i + 1)] + T):
			T += S[-(i + 1)]
		else:
			T = S[-(i + 1)] + T
		i += 1
	print(T)


test = int(input())
for i in range(test):
	n1 = int(input())
	s1 = input()
	l = 0
	m1 = 1
	ar = []
	for i in range(n1):
		if i % 2 == 0:
			if s1[l] == '0':
				ar.insert(0, '0')
			else:
				ar.append('1')
			l += 1
		else:
			if s1[-l] == '1':
				ar.insert(0, '1')
			else:
				ar.append('0')
			m1 += 1
	br = ''.join(ar)
	print(br)


T = int(input())
for i in range(T):
	N = int(input())
	s = input().strip()
	i = 0
	j = N - 1
	t = ''
	while i <= j:
		if s[i] == '0':
			t = s[i] + t
		else:
			t = t + s[i]
		if i < j:
			if s[j] == '0':
				t = t + s[j]
			else:
				t = s[j] + t
			j -= 1
		i += 1
	print(t)


for _ in range(int(input())):
	N = int(input())
	S = input()
	res = ''
	left = 0
	right = N - 1
	while left <= right:
		if S[left] == '0':
			res = S[left] + res
		else:
			res = res + S[left]
		if left < right:
			if S[right] == '0':
				res = res + S[right]
			else:
				res = S[right] + res
			right -= 1
		left += 1
	print(res)


import math
for i in range(int(input())):
	n = int(input())
	a = input()
	t = []
	for x in range(math.ceil(n / 2)):
		if a[x] == '0':
			t = ['0'] + t
		else:
			t.append('1')
		if n - 1 - x != x:
			if a[n - 1 - x] == '1':
				t = ['1'] + t
			else:
				t.append('0')
	print(''.join(t))


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	t = ''
	count = 0
	left = 0
	right = n - 1
	while left <= right:
		count += 1
		if count % 2 != 0:
			a = s[left]
			if t + a > a + t:
				t = a + t
			else:
				t = t + a
			left += 1
		else:
			b = s[right]
			if t + b > b + t:
				t += b
			else:
				t = b + t
			right -= 1
	print(t)


for _ in range(int(input())):
	N = int(input())
	S = list(input())
	result = ''
	left = 0
	right = N - 1
	flag = 1
	while left <= right:
		if flag:
			if S[left] == '0':
				result = S[left] + result
			else:
				result = result + S[left]
			left += 1
		else:
			if S[right] == '0':
				result = result + S[right]
			else:
				result = S[right] + result
			right -= 1
		if flag == 0:
			flag = 1
		else:
			flag = 0
	print(result)


for _ in range(int(input())):
	n = int(input())
	s = input()
	res = ''
	left = 0
	right = len(s) - 1
	flag = 1
	while left <= right:
		if flag:
			if s[left] == '0':
				res = s[left] + res
			else:
				res = res + s[left]
			left += 1
		else:
			if s[right] == '0':
				res = res + s[right]
			else:
				res = s[right] + res
			right -= 1
		if flag == 0:
			flag = 1
		else:
			flag = 0
	print(res)


t1 = int(input())
for ni in range(t1):
	n = int(input())
	s = input()
	t = ''
	for i in range(n // 2):
		if s[i] == '0':
			t = '0' + t
		elif s[i] == '1':
			t = t + '1'
		if s[n - 1 - i] == '1':
			t = '1' + t
		elif s[n - i - 1] == '0':
			t = t + '0'
	if n % 2 != 0:
		if s[n // 2] == '0':
			t = '0' + t
		else:
			t = t + '1'
	print(t)


for _ in range(int(input())):
	n = int(input())
	s = input()
	res = ''
	start = 0
	end = len(s) - 1
	f = 1
	while end >= start:
		if f:
			if s[start] == '0':
				res = s[start] + res
			else:
				res = res + s[start]
			start += 1
		else:
			if s[end] == '0':
				res = res + s[end]
			else:
				res = s[end] + res
			end -= 1
		f = 1 if f == 0 else 0
	print(res)


for _ in range(int(input())):
	n = int(input())
	s = input()
	x = ''
	m = 0
	while s != '':
		if m == 0:
			x += s[0]
			s = s[1:]
		elif m % 2 != 0:
			if s[-1] == '0':
				x = x + s[-1]
				s = s[:len(s) - 1]
			else:
				x = s[-1] + x
				s = s[:len(s) - 1]
		elif m % 2 == 0:
			if s[0] == '0':
				x = s[0] + x
				s = s[1:]
			else:
				x = x + s[0]
				s = s[1:]
		m += 1
	print(x)