Chef has a binary string S. He can modify it by choosing any subsequence of length 3 from it and deleting the first and last character of the subsequence.

For example, if S = \textcolor{red}{11}01\textcolor{red}{0}1, Chef can choose the subsequence marked in red and delete its first and last characters, obtaining the string S = 1011.

Chef wonders what is the lexicographically largest string he can obtain by modifying the original string using a finite number of operations. Please help Chef in this task.

Note: A binary string A is said to be lexicographically larger than another binary string B if:
B is a proper prefix of A (for example, 101 is lexicographically larger than 10); or
There exists an index i such that A_{1} = B_{1}, A_{2} = B_{2}, \ldots, A_{i-1} = B_{i-1} and A_{i} > B_{i}.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of a single line of input containing the original binary string S.

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

For each test case, output on a new line the lexicographically largest string Chef can obtain.

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

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

----- Sample Input 1 ------ 
4
101
1010
0000
0001

----- Sample Output 1 ------ 
101
11
0000
01

----- explanation 1 ------ 
Test case $1$: It is optimal to not perform any moves.

Test case $2$: In one move, by choosing the subsequence $1\textcolor{red}{010}$, the string can be made into $11$, which is the lexicographically largest possible.

Test case $3$: It is optimal to not perform any move.

Difficulty: HARD
Tags: Ad-hoc

Starter code:

Solutions:
for _ in range(int(input())):
	S = input()
	if '1' not in S:
		print(S)
		continue
	k = S.rfind('1')
	suf = S[k:]
	S = S[:k]
	k = S.count('0')
	if k & 1:
		if '0' in suf:
			print(S.replace('0', '') + suf[:-1])
		elif S[-1] == '1':
			print(S.replace('0', ''))
		elif S[-2] == '0':
			print(S.replace('0', '') + '01')
		elif S.rfind('0', 0, -1) - S.find('0') + 1 != k - 1:
			print(S.replace('0', '') + '01')
		else:
			print(S.replace('0', ''))
	elif S.rfind('0') - S.find('0') + 1 != k:
		print(S.replace('0', '') + suf)
	elif len(suf) >= 3:
		print(S.replace('0', '') + suf[:-2])
	elif len(suf) == 2:
		if S[-1] == '1':
			print(S.replace('0', ''))
		else:
			print(S.replace('0', '') + '01')
	elif S.endswith('11'):
		print(S.replace('0', '')[:-1])
	elif S[-1] == '1':
		print(S.replace('0', '')[:-1] + '01')
	else:
		print(S.replace('0', '') + '001')


def dell(a):
	z = ''
	if len(a) >= 3 and a[-1] == '1' and (a[-2] == '1'):
		a[-1] = '$'
		for i in range(len(a)):
			if a[i] == '0':
				a[i] = '$'
				break
		for i in range(len(a)):
			if a[i] != '$':
				z += a[i]
		return [x for x in z]
	else:
		return a

def calc(s):
	T = []
	for (j, i) in enumerate(s):
		if i == '0':
			T.append(j)
	if len(T) == 1:
		return 1
	if T[-1] == T[-2]:
		return 1
	for i in range(T[0], T[-2]):
		if s[i] == '1':
			return 1
	return 2

def solve():
	ans = ''
	banana = input()
	s = [x for x in banana]
	a = ''
	(t, p) = (0, 0)
	for i in range(len(s) - 1, -1, -1):
		if s[i] == '1':
			for j in range(i + 1):
				a += s[j]
			break
		else:
			t += 1
	if t == len(s):
		print(''.join(s))
		return
	s = [x for x in a]
	for i in s:
		if i == '0':
			p += 1
	if p == 0:
		ans += ''.join(s)
		for i in range(t):
			ans += '0'
		print(ans)
		return
	if p % 2 == 0:
		(l, r) = (2147482647, -2147482647)
		for (j, i) in enumerate(s):
			if i == '0':
				l = min(l, j)
				r = max(r, j)
		for i in s[l:r + 1]:
			if i == '1':
				for j in s:
					if j == '1':
						ans += '1'
				for k in range(t):
					ans += '0'
				print(ans)
				return
		if t >= 2:
			for i in s:
				if i == '1':
					ans += '1'
			for i in range(t - 2):
				ans += '0'
			print(ans)
			return
		if t == 1:
			a = ''
			for i in range(len(s) - 1, -1, -1):
				if s[i] == '0':
					s[i] = '$'
					break
			for i in range(len(s)):
				if s[i] == '$':
					a += '0'
				elif s[i] == '1':
					a += '1'
			s = [x for x in a]
			print(''.join(dell(s)))
			return
		if t == 0:
			lol = 0
			a = ''
			for i in range(len(s) - 1, -1, -1):
				if s[i] == '0':
					s[i] = '$'
					lol += 1
					if lol == 2:
						break
			for i in s:
				if i == '$':
					a += '0'
				elif i == '1':
					a += '1'
			s = [x for x in a]
			print(''.join(dell(dell(s))))
			return
	T = 0
	L = calc(s)
	a = ''
	for i in range(len(s) - 1, -1, -1):
		if s[i] == '0':
			T += 1
			if T == L:
				s[i] = '$'
	for i in s:
		if i == '1':
			a += '1'
		elif i == '$':
			a += '0'
	s = [x for x in a]
	if t != 0:
		for i in s:
			if i == '1':
				print('1', end='')
		for i in range(t - 1):
			print('0', end='')
		return
	print(''.join(dell([x for x in a])))
for _ in range(int(input())):
	solve()
	print()


def x(n):
	if not n:
		return n
	if n % 2 == 0:
		return 2
	else:
		return 1
for _ in range(int(input())):
	a = list(input())
	l = len(a)
	a1 = []
	a2 = []
	count = 0
	count1 = 0
	c = 0
	for (i, item) in enumerate(a):
		if item == '0':
			count += 1
			if i == l - 1:
				a1.append(count)
			if count1 > 0:
				a2.append(count1)
				count1 = 0
		else:
			count1 += 1
			if count > 0:
				a1.append(count)
				count = 0
				c += 1
			if not a1:
				a1.append(0)
			if i == l - 1:
				a1.append(count)
				a2.append(count1)
	index = 0
	l1 = len(a1)
	pre = 0
	if not a2:
		s = ''
		for i in range(l1):
			s += '0' * a1[i]
			try:
				s += '1' * a2[i]
			except:
				pass
		print(s)
		continue
	su = sum(a1[:l1 - 1])
	for i in range(l1 - 2, -1, -1):
		if a1[i] != 0:
			pre = i
			break
	if x(su) == 2:
		if c > 1:
			for i in range(l1 - 1):
				a1[i] = 0
		else:
			a1[pre] = 2
	if x(su) == 1:
		if c == 2 and x(a1[pre - 1]) > a1[pre] and (x(a1[pre]) == 1):
			a1[pre - 1] = 1
			a1[pre] = 0
			pre -= 1
		else:
			for i in range(pre):
				a1[i] = 0
			a1[pre] = 1
	if a1[pre] > a1[-1]:
		a1[pre] -= a1[-1]
		a1[-1] = 0
	else:
		a1[-1] -= a1[pre]
		a1[pre] = 0
	index = len(a2) - 1
	while a1[pre]:
		if a2[index] == 1 and pre == index:
			break
		else:
			a2[index] -= 1
			a1[pre] -= 1
	s = ''
	for i in range(l1):
		s += '0' * a1[i]
		try:
			s += '1' * a2[i]
		except:
			pass
	print(s)


def res(s):
	n = len(s)
	z = ''
	if n >= 3 and s[n - 1] == '1' and (s[n - 2] == '1'):
		s = s[:n - 1] + '$'
		for i in range(0, n, 1):
			if s[i] == '0':
				s = s[:i] + '$' + s[i + 1:]
				break
		for i in range(0, n, 1):
			if s[i] != '$':
				z += s[i]
		return z
	else:
		return s

def calc(s):
	n = len(s)
	T = []
	for i in range(0, n, 1):
		if s[i] == '0':
			T.append(i)
	n2 = len(T)
	if n2 == 1:
		return 1
	if T[n2 - 1] == T[n2 - 2]:
		return 1
	for i in range(T[0], T[n2 - 2], 1):
		if s[i] == '1':
			return 1
	return 2

def solve():
	t = 0
	p = 0
	m = ''
	s = input()
	n = len(s)
	for i in range(n - 1, -1, -1):
		if s[i] == '1':
			for j in range(0, i + 1, 1):
				m += s[j]
			break
		else:
			t += 1
	if t == n:
		print(s)
		return 0
	s = m
	n = len(s)
	for i in range(0, n, 1):
		if s[i] == '0':
			p += 1
	if p == 0:
		print(s, end='')
		for j in range(0, t, 1):
			print(0, end='')
		print()
		return 0
	if p % 2 == 0:
		l = 2147482647
		r = -2147483648
		for i in range(0, n, 1):
			if s[i] == '0':
				l = min(l, i)
				r = max(r, i)
		for i in range(l, r + 1, 1):
			if s[i] == '1':
				for j in range(0, n, 1):
					if s[j] == '1':
						print(1, end='')
				for k in range(0, t, 1):
					print(0, end='')
				print()
				return 0
		if t >= 2:
			for i in range(0, n, 1):
				if s[i] == '1':
					print(1, end='')
			for i in range(0, t - 2, 1):
				print(0, end='')
			print()
			return 0
		if t == 1:
			m = ''
			for i in range(n - 1, -1, -1):
				if s[i] == '0':
					s = s[:i] + '$' + s[i + 1:]
					break
			for i in range(0, n, 1):
				if s[i] == '$':
					m += '0'
				elif s[i] == '1':
					m += '1'
			s = m
			n = len(s)
			print(res(s))
			return 0
		if t == 0:
			k = 0
			m = ''
			for i in range(n - 1, -1, -1):
				if s[i] == '0':
					s = s[:i] + '$' + s[i + 1:]
					k += 1
					if k == 2:
						break
			for i in range(0, n, 1):
				if s[i] == '$':
					m += '0'
				elif s[i] == '1':
					m += '1'
			s = m
			n = len(s)
			print(res(res(s)))
			return 0
	T = 0
	L = calc(s)
	m = ''
	for i in range(n - 1, -1, -1):
		if s[i] == '0':
			T += 1
			if T == L:
				s = s[:i] + '$' + s[i + 1:]
	for i in range(0, n, 1):
		if s[i] == '1':
			m += '1'
		elif s[i] == '$':
			m += '0'
	s = m
	n = len(s)
	if t != 0:
		for i in range(0, n, 1):
			if s[i] == '1':
				print(1, end='')
		for i in range(0, t - 1, 1):
			print(0, end='')
		print()
		return 0
	print(res(m))
T = int(input())
for i in range(T):
	solve()


def detect_zero(arg_str):
	fun_str = ''
	arg_str = list(arg_str)
	if len(arg_str) >= 3 and arg_str[len(arg_str) - 1] == '1' and (arg_str[len(arg_str) - 2] == '1'):
		arg_str[len(arg_str) - 1] = '$'
		for i in range(len(arg_str)):
			if arg_str[i] == '0':
				arg_str[i] = '$'
				break
		for i in range(len(arg_str)):
			if arg_str[i] != '$':
				fun_str += arg_str[i]
		return fun_str
	else:
		return ''.join(map(str, arg_str))

def calculation(arg_str):
	temp_arr = []
	for i in range(len(arg_str)):
		if arg_str[i] == '0':
			temp_arr.append(i)
	if len(temp_arr) == 1:
		return 1
	if temp_arr[len(temp_arr) - 1] == temp_arr[len(temp_arr) - 2]:
		return 1
	for i in range(temp_arr[0], temp_arr[len(temp_arr) - 2]):
		if arg_str[i] == '1':
			return 1
	return 2

def solution():
	user_str = input()
	temp_str = ''
	temp_count = 0
	var_count = 0
	for i in range(len(user_str) - 1, -1, -1):
		if user_str[i] == '1':
			for j in range(i + 1):
				temp_str += user_str[j]
			break
		else:
			temp_count += 1
	if temp_count == len(user_str):
		print(user_str)
		return
	user_str = temp_str
	for i in range(len(user_str)):
		if user_str[i] == '0':
			var_count += 1
	if var_count == 0:
		print(user_str, end='')
		for i in range(temp_count):
			print('0', end='')
		print()
		return
	if var_count % 2 == 0:
		low_range = 2147483647
		run_range = -2147483648
		for i in range(len(user_str)):
			if user_str[i] == '0':
				low_range = min(low_range, i)
				run_range = max(run_range, i)
		for i in range(low_range, run_range + 1):
			if user_str[i] == '1':
				for j in range(len(user_str)):
					if user_str[j] == '1':
						print('1', end='')
				for j in range(temp_count):
					print('0', end='')
				print()
				return
		if temp_count >= 2:
			for i in range(len(user_str)):
				if user_str[i] == '1':
					print('1', end='')
			for i in range(temp_count - 2):
				print('0', end='')
			print()
			return
		if temp_count == 1:
			temp_str = ''
			user_str = list(user_str)
			for i in range(len(user_str) - 1, -1, -1):
				if user_str[i] == '0':
					user_str[i] = '$'
					break
			for i in range(len(user_str)):
				if user_str[i] == '$':
					temp_str += '0'
				elif user_str[i] == '1':
					temp_str += '1'
			user_str = temp_str
			print(detect_zero(user_str))
			print()
			return
		if temp_count == 0:
			_ = 0
			temp_str = ''
			user_str = list(user_str)
			for i in range(len(user_str) - 1, -1, -1):
				if user_str[i] == '0':
					user_str[i] = '$'
					_ += 1
					if _ == 2:
						break
			for i in range(len(user_str)):
				if user_str[i] == '$':
					temp_str += '0'
				elif user_str[i] == '1':
					temp_str += '1'
			user_str = temp_str
			print(detect_zero(detect_zero(user_str)))
			print()
			return
	temp = 0
	t_temp = calculation(user_str)
	temp_str = ''
	user_str = list(user_str)
	for i in range(len(user_str) - 1, -1, -1):
		if user_str[i] == '0':
			temp += 1
			if temp == t_temp:
				user_str[i] = '$'
	for i in range(len(user_str)):
		if user_str[i] == '1':
			temp_str += '1'
		elif user_str[i] == '$':
			temp_str += '0'
	user_str = temp_str
	if temp_count != 0:
		for i in range(len(user_str)):
			if user_str[i] == '1':
				print('1', end='')
		for i in range(temp_count - 1):
			print('0', end='')
		print()
		return
	print(detect_zero(temp_str))
	print()
for tries in range(int(input())):
	solution()


def split(s):
	i = len(s) - 1
	while i > -1 and s[i] == '0':
		i -= 1
	i += 1
	return (s[:i], s[i:])

def get_groups(s):
	res = []
	if len(s) == 0:
		return res
	current = s[0]
	for i in range(1, len(s)):
		if s[i] == current[0]:
			current += s[i]
		else:
			res.append(current)
			current = s[i]
	res.append(current)
	return res

def get_updated_sl(gs):
	groups = gs[:]
	res = []
	zeroes_indices = []
	even_zeroes_indices = []
	odd_zeroes_indices = []
	for (i, g) in enumerate(groups):
		if g[0] == '0':
			zeroes_indices.append(i)
			if len(g) % 2 == 0:
				even_zeroes_indices.append(i)
			else:
				odd_zeroes_indices.append(i)
	if len(zeroes_indices) > 0:
		if len(even_zeroes_indices) % 2 == 0:
			if len(odd_zeroes_indices) % 2 == 0:
				for i in zeroes_indices:
					groups[i] = ''
			else:
				for i in zeroes_indices[:-1]:
					groups[i] = ''
				groups[zeroes_indices[-1]] = '0'
		else:
			i = even_zeroes_indices[-1]
			if i != zeroes_indices[0]:
				if (len(zeroes_indices) - 1) % 2 == 0:
					for i in zeroes_indices:
						groups[i] = ''
				else:
					for i in zeroes_indices[:-1]:
						groups[i] = ''
					groups[zeroes_indices[-1]] = '0'
			elif len(zeroes_indices) > 1 and len(groups[zeroes_indices[1]]) > 2 or len(zeroes_indices) > 2:
				if (len(zeroes_indices) - 1) % 2 == 0:
					for i in zeroes_indices:
						groups[i] = ''
				else:
					for i in zeroes_indices[:-1]:
						groups[i] = ''
					groups[zeroes_indices[-1]] = '0'
			elif len(zeroes_indices) > 1:
				groups[zeroes_indices[1]] = ''
				groups[zeroes_indices[0]] = '0'
			else:
				groups[zeroes_indices[0]] = '00'
	res = ''.join(groups)
	return res

def f(s):
	(sl, sr) = split(s)
	if len(sl) == 0:
		return s
	groups = get_groups(sl)
	sl = get_updated_sl(groups)
	if len(sr) > 0:
		sl_zeroes_indices = []
		deleted_indices = []
		for (i, c) in enumerate(sl):
			if c == '0':
				sl_zeroes_indices.append(i)
		assert len(sl_zeroes_indices) < 3
		count = len(sr)
		for j in sl_zeroes_indices:
			if count > 0:
				deleted_indices.append(j)
				count -= 1
		sl = ''.join([c for (z, c) in enumerate(sl) if z not in deleted_indices])
		sr = sr[:len(sr) - len(deleted_indices)]
	sl_zeroes_indices = []
	for (i, c) in enumerate(sl):
		if c == '0':
			sl_zeroes_indices.append(i)
	assert len(sl_zeroes_indices) < 3, (s, sl, sr)
	if len(sl_zeroes_indices) == 1:
		i = sl_zeroes_indices[0]
		if len(sl[i + 1:]) > 1:
			sl = ''.join([c for (z, c) in enumerate(sl) if z != i and z != i + 2])
	if len(sl_zeroes_indices) == 2:
		i = sl_zeroes_indices[0]
		if len(sl[i + 1:]) > 3:
			sl = ''.join([c for (z, c) in enumerate(sl) if z != i and z != i + 1 and (z != i + 2) and (z != i + 4)])
		elif len(sl[i + 1:]) > 2:
			sl = ''.join([c for (z, c) in enumerate(sl) if z != i and z != i + 2])
	return sl + sr
t = int(input())
for i in range(t):
	s = input()
	print(f(s))


def T(S, N, x):
	if x == 0:
		return 0
	else:
		x1 = S.rfind('0')
		x2 = S.index('0')
		if x % 2 == 0:
			if x1 - x2 + 1 == x:
				return 2
			else:
				return 0
		else:
			return 1
a = int(input())
for i in range(a):
	S = input()
	k = S.rfind('1')
	x = S.count('0')
	N = len(S)
	if x == 0:
		B = '1' * N
	elif x == N:
		B = '0' * N
	elif N <= 2:
		B = S
	else:
		x1 = S.rfind('0')
		x2 = S.index('0')
		C = S[:k + 1]
		p = x - (N - 1 - k)
		q = T(C, k + 1, p)
		if N - 1 - k >= q:
			B = '1' * (N - x)
			B += '0' * (N - 1 - k - q)
		elif N - 1 - k == 1:
			if N - x2 - x >= 2:
				B = '1' * (N - x - 1)
			else:
				B = '1' * x2
				B += '01'
		elif q == 2:
			if N - x2 - x >= 3:
				B = '1' * (N - x - 2)
			elif N - x2 - x <= 1:
				B = '1' * x2
				B += '00'
				B += '1' * (N - x2 - x)
			else:
				B = '1' * x2
				B += '0'
				B += '1' * (N - x - 1 - x2)
		else:
			D = S[:x1]
			t = T(D, x1, x - 1)
			if t == 0:
				if x1 == N - 2:
					B = '1' * (N - x - 1)
					B += '01'
				else:
					B = '1' * (N - x - 1)
			elif D[x1 - 1] == '1':
				B = '1' * (N - x - 1)
			elif x1 == N - 2:
				B = '1' * (N - x - 1)
				B += '01'
			else:
				B = '1' * (N - x - 1)
	print(B)


t = int(input())

def display(n):
	tmp = '1' * n
	print(tmp, end='')

def cnt1(s, start, end):
	ss = s[start:end]
	return ss.count('1')

def cnt2(s, start, end):
	ss = s[start:end]
	return ss.count('0')

def test(s):
	x = s.rfind('0')
	y = s.rfind('1')
	if x > y:
		display(cnt1(s, 0, len(s)))
		print('0')
	elif y > x and s[y] != s[y - 1]:
		display(cnt1(s, 0, len(s)) - 1)
		print('01')
	else:
		display(cnt1(s, 0, len(s)) - 1)
		print()

def test3(s):
	x = s.rfind('0')
	y = s.rfind('1')
	if x > y:
		display(cnt1(s, 0, len(s)))
		print('0')
	elif y > x and s[y] != s[y - 1]:
		display(cnt1(s, 0, len(s)) - 1)
		print('01')
	else:
		display(cnt1(s, 0, len(s)) - 1)
		print()

def test2(s, c1, c2):
	x = s.rfind('0')
	y = s.rfind('1')
	l = len(s)
	if y > x and s[y] == s[y - 1]:
		display(cnt1(s, 0, l) - 1)
		print()
	elif c1 > 1 and c2 > 1:
		test3(s)
	elif c1 == 1:
		test3(s)
	else:
		i = s.find('0')
		display(cnt1(s, 0, i))
		if cnt1(s, i, l) > 1:
			display(cnt1(s, i, l) - 1)
		else:
			print('0', end='')
			display(cnt1(s, i, l))
		print()

def solve3(s):
	(x, l) = (0, len(s))
	(cc1, cc2) = (0, 0)
	while x < l and s[x] != '0':
		x += 1
	while x < l and s[x] == '0':
		x += 1
		cc1 += 1
	while x < l and s[x] != '0':
		x += 1
	tt = x
	while x < l and s[x] == '0':
		x += 1
		cc2 += 1
	while x < l and s[x] != '0':
		x += 1
	if tt == l:
		test(s)
	elif x == l:
		test2(s, cc1, cc2)
	else:
		test3(s)

def solve2(s, z):
	x = 0
	tt = x
	while x < z and s[x] == '1':
		x += 1
	tt = x
	while x < z and s[x] == '0':
		x += 1
	uu = x
	while x < z and s[x] == '1':
		x += 1
	if x == z:
		display(cnt1(s, 0, tt))
		if cnt1(s, uu, z) <= 1:
			print('00', end='')
			display(cnt1(s, uu, z))
		elif cnt1(s, uu, z) == 2:
			print('0', end='')
			display(cnt1(s, uu, z) - 1)
		else:
			display(cnt1(s, uu, z) - 2)
		print()
	else:
		display(cnt1(s, 0, z))
		print()

def solve1(s, x):
	display(cnt1(s, 0, x + 1))
	l = len(s)
	if cnt2(s, 0, x + 1) % 2 == 1:
		for m in range(x + 1, l - 1):
			print(s[m], end='')
	else:
		kk = x
		while kk >= 0 and s[kk] != '0':
			kk -= 1
		while kk >= 0 and s[kk] == '0':
			kk -= 1
		while kk >= 0 and s[kk] != '0':
			kk -= 1
		if cnt2(s, 0, x + 1) == 0:
			for m in range(x + 1, l):
				print(s[m], end='')
		elif kk == -1:
			for m in range(x + 1, l - 2):
				print(s[m], end='')
		else:
			for m in range(x + 1, l):
				print(s[m], end='')
	print()
for _ in range(t):
	s = input()
	l = len(s)
	ones = s.count('1')
	zeroes = l - ones
	i = l - 1
	while i >= 0 and s[i] == '0':
		i -= 1
	if zeroes == 0 or zeroes == l:
		print(s)
	elif l - i - 1 > 1:
		solve1(s, i)
	elif zeroes % 2 == 0:
		solve2(s, l)
	else:
		solve3(s)


from sys import stdin
input = stdin.readline

def almostsolve(S):
	zeros = [i for i in range(len(S)) if S[i] == '0']
	if len(zeros) == 0 or len(S) - len(zeros) == 0 or len(S) < 3:
		return S
	zones = []
	rightmost = None
	i = 0
	while i < len(zeros):
		start = i
		while i + 1 < len(zeros) and zeros[i + 1] == zeros[i] + 1:
			i += 1
		i += 1
		zones.append(i - start)
		if (i - start) % 2 == 0:
			rightmost = zeros[i - 1]
	assert sum(zones) == len(zeros)
	if S[-1] == '0':
		if len(zones) == 1:
			return S
		elif len(zones) == 2:
			if zones[0] % 2 == 0:
				count = 2
			else:
				count = 1
			if count == 1:
				return '1' * (len(S) - len(zeros)) + '0' * (zones[-1] - 1)
			elif count == 2 and zones[-1] >= 2:
				return '1' * (len(S) - len(zeros)) + '0' * (zones[-1] - 2)
			else:
				before = sum((1 for i in range(rightmost) if S[i] == '1'))
				after = len(S) - len(zeros) - before
				v1 = '1' * before + '0' + '1' * after
				v2 = v1
				if before >= 2 or after >= 2:
					v2 = '1' * (before + after - 1)
				return max(v1, v2)
		else:
			even = sum((1 for zone in zones[:-1] if zone % 2 == 0))
			odd = sum((1 for zone in zones[:-1] if zone % 2 == 1))
			if odd % 2 == 0 and (not (even == 1 and odd == 0)):
				return '1' * (len(S) - len(zeros)) + '0' * zones[-1]
			else:
				return '1' * (len(S) - len(zeros)) + '0' * (zones[-1] - 1)
	elif len(zones) == 1:
		if len(zeros) % 2 == 0:
			count = 2
		else:
			count = 1
		before = zeros[0]
		after = len(S) - len(zeros) - zeros[0]
		v1 = '1' * before + '0' * count + '1' * after
		v2 = v1
		if count == 2:
			if before >= 3 or (before >= 2 and after >= 1) or (before >= 1 and after >= 2) or (after >= 3):
				v2 = '1' * (before + after - 2)
		v3 = v1
		if count == 2:
			if after >= 1:
				v3 = '1' * before + '0' + '1' * (after - 1)
			elif before >= 1:
				v3 = '1' * (before - 1) + '0' + '1' * after
		elif before >= 2 or after >= 2:
			v3 = '1' * (before + after - 1)
		return max(v1, v2, v3)
	else:
		even = sum((1 for zone in zones if zone % 2 == 0))
		odd = sum((1 for zone in zones if zone % 2 == 1))
		if odd % 2 == 0 and (not (even == 1 and odd == 0)):
			return '1' * (len(S) - len(zeros))
		elif odd == 1 and even == 1:
			before = sum((1 for i in range(rightmost) if S[i] == '1'))
			after = len(S) - len(zeros) - before
			v1 = '1' * before + '0' + '1' * after
			v2 = v1
			if before >= 2 or after >= 2:
				v2 = '1' * (before + after - 1)
			return max(v1, v2)
		else:
			before = zeros[-1] - len(zeros) + 1
			after = len(S) - len(zeros) - before
			v1 = '1' * before + '0' + '1' * after
			v2 = v1
			if before >= 2 or after >= 2:
				v2 = '1' * (before + after - 1)
			return max(v1, v2)

def solve(S):
	if len(S) < 3:
		return S
	S1 = almostsolve(S)
	S2 = S1
	if S[-1] == '1' and S[-2] == '0':
		S2 = almostsolve(S[:-1]) + '1'
		S2 = almostsolve(S2)
	return max(S1, S2)
T = int(input().strip())
for problem in range(1, T + 1):
	S = input().strip()
	print(solve(S))


t = int(input())

def allsame(s):
	for i in range(1, len(s)):
		if s[i] != s[i - 1]:
			return False
	return True

def downsize(s):
	i = 0
	count = 0
	news = []
	patches = [0, 0, 0]
	for i in range(len(s)):
		if s[i] == '0':
			count += 1
		elif count != 0 and count % 2 == 0:
			news += ['0', '0', '1']
			count = 0
			patches[2] += 1
		elif count != 0 and count % 2 == 1:
			news += ['0', '1']
			count = 0
			patches[1] += 1
		else:
			news.append('1')
			count = 0
	if count != 0:
		news += ['0' for _ in range(count)]
		patches[0] = count
	return (''.join(news), patches)

def onepatcharray(s, patchsize, convertedonepatch):
	news = [0, 0, 0]
	patchinserted = False
	for i in range(len(s) - 1, -1, -1):
		if s[i] == '0':
			if patchinserted:
				continue
			if convertedonepatch:
				if s[i - 1] == '0':
					news[1] = patchsize
					patchinserted = True
			else:
				news[1] = patchsize
				patchinserted = True
		elif patchinserted:
			news[0] += 1
		else:
			news[2] += 1
	return news

def removelastpatch(arr):
	if arr[-1] == 0:
		return '1' * arr[0] + '0' * arr[1]
	elif arr[2] > arr[1]:
		return '1' * (arr[0] + arr[2] - arr[1])
	elif arr[2] == arr[1]:
		return '1' * arr[0] + '0' + '1' * (arr[2] - arr[1] + 1)
	else:
		return '1' * arr[0] + '0' * arr[1] + '1' * arr[2]
while t > 0:
	t -= 1
	s = input()
	copy = s
	if allsame(s):
		print(s)
		continue
	(s, patches) = downsize(s)
	if len(s) == 2:
		print(s)
		continue
	i = 0
	j = 1
	convertedonepatch = False
	if patches[2] > 1:
		patches[2] = 0
	elif patches[2] == 1:
		if patches[1] == 1 and s[::-1].index('0') < s[::-1].index('00'):
			passed = False
			l = 0
			for i in range(len(copy) - 1, -1, -1):
				if copy[i] == '0':
					passed = True
					l += 1
				elif passed:
					break
			if l > 1:
				patches[2] = 0
	if patches[2] == 1:
		if patches[0] + patches[1] >= 2:
			patches[2] = 0
			rem = min(2, patches[1])
			patches[1] -= rem
			patches[0] -= 2 - rem
		else:
			patches[2] -= patches[0] + patches[1]
			if patches[1] == 1 or patches[0] == 1:
				convertedonepatch = True
				patches[1] = 1
			patches[0] = 0
	else:
		pass
	patches[1] %= 2
	if patches[1] == 1 and patches[0] > 0:
		patches[1] = 0
		patches[0] -= 1
	patchsize = patches[0] + patches[1] + patches[2] * 2
	arr = onepatcharray(s, patchsize, convertedonepatch)
	if patchsize == 0:
		print('1' * (arr[0] + arr[2]))
		continue
	s = removelastpatch(arr)
	print(s)


def f1(s):
	x = ''
	if len(s) >= 3 and s[-1] == 1 and (s[-2] == 1):
		s[-1] = 9
		for i in range(len(s)):
			if s[i] == 0:
				s[i] = 9
				break
		for i in range(len(s)):
			if s[i] != 9:
				x += str(s[i])
		return list((int(i) for i in x))
	else:
		return s

def f2(s):
	l = []
	for i in range(len(s)):
		if s[i] == 0:
			l.append(i)
	if len(l) == 1:
		return 1
	if l[-1] == l[-2]:
		return 1
	for i in range(l[0], l[-2]):
		if s[i] == 1:
			return 1
	return 2

def f(s):
	(t, p, a) = (0, 0, '')
	for i in range(len(s) - 1, -1, -1):
		if s[i] == 1:
			for j in range(i + 1):
				a += str(s[j])
			break
		else:
			t += 1
	if t == len(s):
		print(''.join((str(i) for i in s)))
		return
	s = list((int(i) for i in a))
	for i in range(len(s)):
		if s[i] == 0:
			p += 1
	if p == 0:
		print(''.join((str(i) for i in s)) + '0' * t)
		return
	if p % 2 == 0:
		(l, r) = (int(3000000000.0), -1 * int(3000000000.0))
		for i in range(len(s)):
			if s[i] == 0:
				(l, r) = (min(l, i), max(r, i))
		for i in range(l, r + 1):
			if s[i] == 1:
				x = ''
				for j in range(len(s)):
					if s[j] == 1:
						x += str(s[j])
				print(x + '0' * t)
				return
		if t >= 2:
			x = ''
			for i in range(len(s)):
				if s[i] == 1:
					x += str(s[i])
			print(x + '0' * (t - 2))
			return
		if t == 1:
			a = ''
			for i in range(len(s) - 1, -1, -1):
				if s[i] == 0:
					s[i] = 9
					break
			for i in range(len(s)):
				if s[i] == 9:
					a += '0'
				elif s[i] == 1:
					a += '1'
			s = list((int(i) for i in a))
			print(''.join((str(i) for i in f1(s))))
			return
		if t == 0:
			(c, a) = (0, '')
			for i in range(len(s) - 1, -1, -1):
				if s[i] == 0:
					s[i] = 9
					c += 1
					if c == 2:
						break
			for i in range(len(s)):
				if s[i] == 9:
					a += '0'
				elif s[i] == 1:
					a += '1'
			s = list((int(i) for i in a))
			print(''.join((str(i) for i in f1(f1(s)))))
			return
	(w, h, a) = (0, f2(s), '')
	for i in range(len(s) - 1, -1, -1):
		if s[i] == 0:
			w += 1
			if w == h:
				s[i] = 9
	for i in range(len(s)):
		if s[i] == 1:
			a += '1'
		elif s[i] == 9:
			a += '0'
	s = list((int(i) for i in a))
	if t != 0:
		x = ''
		for i in range(len(s)):
			if s[i] == 1:
				x += str(s[i])
		print(x + '0' * (t - 1))
		return
	a = list((int(i) for i in a))
	print(''.join((str(i) for i in f1(a))))
	return
for _ in range(int(input())):
	s = list((int(i) for i in input()))
	f(s)