Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given a binary string $S$. Chef defines $\mathrm{MEX}(S)$ as the smallest non-negative integer such that its binary representation (without leading '0'-s; in particular, the binary representation of $0$ is "0") is not a [subsequence] of $S$.

Chef is asking you to find $\mathrm{MEX}(S)$. Since this integer could be very large, find its binary representation (without leading '0'-s).

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains a single string $S$.

------  Output ------
For each test case, print a single line containing one string: $\mathrm{MEX}(S)$ in binary representation.

------  Constraints ------
$1 ≤ T ≤ 10^{5}$
$1 ≤ |S| ≤ 10^{6}$
$S$ contains only characters '0' and '1'
the sum of $|S|$ over all test cases does not exceed $2 \cdot 10^{6}$

------  Subtasks ------
Subtask #1 (20 points): 
- $1 ≤ T ≤  2 \cdot 10^{3}$
$|S| ≤ 10$

Subtask #2 (20 points): 
- $1 ≤ T ≤  10^{5}$
$|S| ≤ 60$

Subtask #2 (60 points):
- original constraints

----- Sample Input 1 ------ 
2

1001011

1111
----- Sample Output 1 ------ 
1100

0
----- explanation 1 ------ 
Example case 1: All integers between $0$ and $11$ inclusive, in binary representation, appear in $S$ as subsequences. However, the binary representation of $12$ (which is "1100") is not a subsequence of $S$.

Example case 2: Since $S$ contains only '1'-s, the string "0" is not a subsequence of $S$ and therefore $\mathrm{MEX}(S) = 0$.

Difficulty: HARD
Tags: Dynamic programming

Combinatorics

Data structures
Skill types: Dynamic programming

Data structures

Starter code:

Solutions:
t = int(input())
for i in range(0, t):
	s = input()
	l = len(s)
	next0 = [-1 for x in range(0, l)]
	next1 = [-1 for x in range(0, l)]
	lens = [0 for x in range(0, l)]
	j = l - 1
	z = o = 0
	c = 1
	n0 = -1
	n1 = -1
	while j >= 0:
		lens[j] = c
		next0[j] = n0
		next1[j] = n1
		if s[j] == '0':
			z = 1
			n0 = j
		else:
			o = 1
			n1 = j
		if z == 1 & o == 1:
			c = c + 1
			z = o = 0
		j = j - 1
	if n0 == -1:
		print('0')
		continue
	if n1 == -1:
		print('1')
		continue
	str = ''
	j = n1
	while True:
		str = str + s[j]
		if next0[j] == -1:
			str = str + '0'
			break
		elif next1[j] == -1:
			str = str + '1'
			break
		elif lens[next0[j]] <= lens[next1[j]]:
			j = next0[j]
		else:
			j = next1[j]
	print(str)


t = int(input())
for _ in range(t):
	s = input()
	s_len = len(s)
	next0 = [-1] * s_len
	lastpos = -1
	for i in range(s_len):
		if s[i] == '0':
			for j in range(lastpos + 1, i + 1):
				next0[j] = i
			lastpos = i
	for i in range(lastpos + 1, s_len):
		next0[i] = s_len
	if next0[0] == s_len:
		print('0')
		continue
	next1 = [-1] * s_len
	lastpos = -1
	for i in range(s_len):
		if s[i] == '1':
			for j in range(lastpos + 1, i + 1):
				next1[j] = i
			lastpos = i
	for i in range(lastpos + 1, s_len):
		next1[i] = s_len
	dp = [-1] * (s_len + 2)
	dp1 = [-1] * (s_len + 2)
	dp[s_len] = dp[s_len + 1] = 0
	dp1[s_len] = dp1[s_len + 1] = 0
	for i in range(s_len - 1, -1, -1):
		dp[i] = dp[i + 1]
		if s[i] == '0' and next1[i] < s_len:
			dp[i] = max(dp[i], dp[next1[i] + 1] + 1)
		if s[i] == '1' and next0[i] < s_len:
			dp[i] = max(dp[i], dp[next0[i] + 1] + 1)
		dp1[i] = dp1[i + 1]
		if next1[i] < s_len:
			dp1[i] = max(dp1[i], dp[next1[i] + 1] + 1)
	a_len = dp1[0] + 1
	curr_id = next1[0] + 1
	ans = '1'
	for i in range(1, a_len):
		if curr_id >= s_len:
			ans += '0'
			continue
		if next0[curr_id] >= s_len:
			ans += '0'
			curr_id = next0[curr_id] + 1
			continue
		if dp[next0[curr_id] + 1] < a_len - i - 1:
			ans += '0'
			curr_id = next0[curr_id] + 1
		else:
			ans += '1'
			curr_id = next1[curr_id] + 1
	print(ans)


T = int(input())
for _ in range(T):
	S = input()
	n = len(S)
	lenA = [0 for _ in range(n)]
	count = 0
	one = zero = False
	for i in range(n - 1, -1, -1):
		lenA[i] = count
		if S[i] == '0':
			zero = True
		else:
			one = True
		if one and zero:
			count += 1
			one = zero = False
	next1 = [None] * n
	next0 = [None] * n
	one = zero = None
	for i in range(n - 1, -1, -1):
		next1[i] = one
		next0[i] = zero
		if S[i] == '0':
			zero = i
		else:
			one = i
	if one == None:
		print(1)
	elif zero == None:
		print(0)
	else:
		result = ['1']
		i = one
		while True:
			if next0[i] == None:
				result.append('0')
				break
			elif next1[i] == None:
				result.append('1')
				break
			if lenA[next1[i]] >= lenA[next0[i]]:
				i = next0[i]
				result.append('0')
			else:
				i = next1[i]
				result.append('1')
		print(''.join(result))


for _ in range(int(input())):
	s = input()
	inf = 10 ** 6
	n = len(s)
	next0 = [inf] * n
	next1 = [inf] * n
	n0 = inf
	n1 = inf
	for i in range(n - 1, -1, -1):
		next0[i] = n0
		next1[i] = n1
		if s[i] == '1':
			n1 = i
		else:
			n0 = i
	if n1 == inf:
		print('1')
		continue
	if n0 == inf:
		print('0')
		continue
	len1 = [0] * n
	one = False
	zero = False
	cnt = 0
	for i in range(n - 1, -1, -1):
		len1[i] = cnt
		if s[i] == '1':
			one = True
		if s[i] == '0':
			zero = True
		if one and zero:
			cnt += 1
			one = False
			zero = False
	ans = []
	curr = n1
	while True:
		ans.append(str(s[curr]))
		p0 = next0[curr]
		p1 = next1[curr]
		if p0 == inf:
			ans.append('0')
			break
		elif p1 == inf:
			ans.append('1')
			break
		elif len1[p0] <= len1[p1]:
			curr = p0
		else:
			curr = p1
	print(''.join(ans))


def q1():
	s = list(map(int, input().split()))
	s1 = list(map(int, input().split()))
	l = [0, 0]
	for i in range(3):
		if s[i] > s1[i]:
			l[0] += 1
		elif s[i] < s1[i]:
			l[1] += 1
	print(*l, sep=' ')

def q3():

	def add1(x, y):
		if -1 < x < 6 and -1 < y < 6 and ((x, y) not in his) and (not l[x][y]):
			his.add((x, y))
			todo.append([x, y])
	l = [list(map(int, input().split())) for _ in range(6)]
	todo = [[0, 0]]
	his = set()
	while todo:
		(x, y) = todo.pop()
		if x == 5 and y == 5:
			return 'Yes'
		add1(x + 1, y)
		add1(x - 1, y)
		add1(x, y + 1)
		add1(x, y - 1)
	return 'No'

def zeros():
	for _ in range(int(input())):
		c = 0
		num = 5
		inp = int(input())
		r = inp // num
		while r:
			c += r
			num *= 5
			r = inp // num
		print(c)

def gennum(k, num1, num2):
	s = num1 + num2
	ans = str(num1) + str(num2)
	tocheck = '8624'
	for i in range(k - 2):
		a = str(s)[-1]
		s += int(a)
		ans += a
		if ans[-4:] == tocheck:
			left = k - i - 3
			r = left % 4
			s += 20 * (left // 4)
			if r >= 1:
				s += 8
			if r >= 2:
				s += 6
			if r == 3:
				s += 2
			break
	return s

def divby3():
	for _ in range(int(input())):
		(k, n, n1) = map(int, input().split())
		if not (n + n1) % 10:
			print('NO')
		elif not (n + n1) % 5:
			print('NO' if (n + n1 + 5) % 3 else 'YES')
		else:
			print('NO' if gennum(k, n, n1) % 3 else 'YES')

def coinflip():

	def c(coin, cs):
		if cs == 1:
			if coin % 2:
				return coin // 2 + 1
		return coin // 2
	for _ in range(int(input())):
		for _ in range(int(input())):
			(state, coins, q) = map(int, input().split())
			if state == 1:
				print(c(coins, 2) if q == 1 else c(coins, 1))
			else:
				print(c(coins, 2) if q == 2 else c(coins, 1))

def q2():
	for _ in range(int(input())):
		s = int(input())
		ma = 0
		sum1 = 0
		for i in input().split():
			sum1 += int(i)
			ma = max(ma, int(i))
		print('Yes' if sum1 - ma * 2 > 0 else 'No')

def q4():

	def rc(s, s1):
		c = 0
		if len(s1) != mnum:
			return False
		while c < mnum + 1 and s != s1:
			s1 = s1[-1] + s1[:-1]
			c += 1
		if c >= mnum + 1:
			return False
		return c
	num = int(input())
	s = input().rstrip()
	mal = 0
	mnum = len(s)
	minc = 0
	maxc = 0
	for _ in range(num - 1):
		res = rc(s, input().rstrip())
		if res is False:
			return -1
		if res:
			minc += mnum - res
			maxc -= res
			mal = max(res, mal)
	return min(maxc + mal * num, minc)

def q1cook():
	for _ in range(int(input())):
		(w1, w2, xl, xm, m) = map(int, input().split())
		if xl * m <= w2 - w1 <= xm * m:
			print(1)
		else:
			print(0)

def q2cook():
	for _ in range(int(input())):
		print(input().replace('party', 'pawri'))

def q3cook():
	for _ in range(int(input())):
		l = []
		for i in range(1, 9999):
			if i * i <= 10 ** 6:
				l.append(i * i)
			else:
				break
		print(l)
		for i in l:
			print(i)
			s = input()
			if s == '1':
				break
import sys
input = sys.stdin.readline

def xor():

	def findxor(n):
		r = n % 4
		if not r:
			return n
		if r == 1:
			return 1
		if r == 2:
			return n + 1
		return 0

	def s(a, b):
		return findxor(a - 1) ^ findxor(b)
	for _ in range(int(input())):
		(r, c, num) = map(int, input().split())
		ans = 0
		for i in range(1, c + 1):
			n = num + i
			ans = ans ^ s(n + 1, n + r)
		print(ans)

def deletions():

	def m(i):
		nonlocal t
		a = int(i)
		if a:
			t += 1
		return a
	for _ in range(int(input())):
		(n, seg) = map(int, input().split())
		t = 0
		l = list(map(m, input().split()))
		c = 0
		nowsum = sum(l[:seg])
		min1 = float('inf')
		if nowsum:
			min1 = nowsum
		for i in range(1, n - seg + 1):
			if l[i - 1]:
				nowsum -= 1
			if l[i + seg - 1]:
				nowsum += 1
			if nowsum:
				if nowsum < min1:
					min1 = nowsum
		if min1 == float('inf'):
			print(0)
			continue
		if min1 % 2:
			c += (min1 + 1) * (min1 // 2) + min1 // 2 + 1
		else:
			c += (min1 + 1) * (min1 // 2)
		print(c + t - min1)

def xor2():
	for _ in range(int(input())):
		ans = 0
		(n, m, k) = map(int, input().split())
		for i in range(2, n + m + 1):
			r = i - 1
			if n < r:
				if min(n, m - (r - n + 1) + 1) % 2:
					ans ^= i + k
			elif min(r, m) % 2:
				ans ^= i + k
		print(ans)

def maxearn():
	for _ in range(int(input())):
		res = 0
		for _ in range(int(input())):
			(store, people, p) = map(int, input().split())
			pr = people // (store + 1) * p
			if res < pr:
				res = pr
		print(res)

def movies():
	for _ in range(int(input())):
		(n, x) = map(int, input().split())
		ans = 0
		for _ in range(n):
			(space, rate) = input().split()
			if int(space) <= x:
				if ans < int(rate):
					ans = int(rate)
		print(ans)
import math

def turnit():
	for _ in range(int(input())):
		(velo, maxv, maxdecre, daway) = map(int, input().split())
		if velo <= maxv:
			print('yes')
			continue
		if velo > maxdecre:
			v = velo * velo - 2 * (velo - maxdecre) * daway
			while v < 0:
				v += 2 * daway
			v = math.sqrt(v)
		else:
			v = velo * velo - 2 * daway
			if v < 0:
				v = velo
			else:
				v = math.sqrt(v)
		if v < maxv:
			print('yes')
		else:
			print('no')

def racing():
	for _ in range(int(input())):
		(sec, dt, mt) = input().split()
		dt = int(dt) * 60
		m = min(dt, int(sec))
		res = m
		dt -= m
		res += dt * 2
		print('YES' if res <= int(mt) * 60 else 'NO')

def light():
	for _ in range(int(input())):
		(arrivetime, timemax, ability) = map(int, input().split())
		candlesall = arrivetime * ability + 1
		if arrivetime >= timemax:
			candlesdead = (arrivetime - timemax) * ability + 1
			print(candlesall - candlesdead)
		else:
			print(candlesall)

def lunchtime():
	for _ in range(int(input())):
		num = int(input())
		l = input().split()
		ans = []
		for i in range(num):
			nowv = int(l[i])
			c = 0
			for left in range(i - 1, -1, -1):
				v = int(l[left])
				if v == nowv:
					c += 1
				elif v > nowv:
					break
			for right in range(i + 1, num):
				v = int(l[right])
				if v == nowv:
					c += 1
				elif v > nowv:
					break
			ans.append(c)
		print(*ans, sep=' ')

def turncor():
	for _ in range(int(input())):
		(u, v, a, s) = map(int, input().split())
		if v * v >= u * u - 2 * a * s:
			print('yes')
		else:
			print('no')

def makeeven():
	for _ in range(int(input())):
		num = int(input())
		s = 0
		t = False
		for i in input().split():
			v = int(i)
			s += v
			if v == 2:
				t = True
		if s % 2:
			print(1 if t else -1)
		else:
			print(0)
import collections

def lunchtimecor():
	for _ in range(int(input())):
		l = collections.deque()
		num = int(input())
		ans = [0] * num
		c = 0
		counter = collections.defaultdict(int)
		for i in input().split():
			nv = int(i)
			if l:
				dv = 0
				while l and l[-1][0] < nv:
					t = l.pop()
					if not dv:
						dv = t[0]
					elif dv != t[0]:
						counter[dv] = 0
						dv = t[0]
					ans[t[1]] = counter[t[0]] - 1
				if dv:
					counter[dv] = 0
			counter[nv] += 1
			l.append([nv, c])
			c += 1
		for i in l:
			ans[i[1]] = counter[i[0]] - 1
		print(*ans, sep=' ')
import collections

def pair():
	if max(list(collections.Counter(map(int, input().split())).values())) > 1:
		print('yes')
	else:
		print('no')

def worldrec():
	for _ in range(int(input())):
		(k1, k2, k3, v) = map(float, input().split())
		num = round(100 / (k1 * k2 * k3 * v), 2)
		print('yes' if num < 9.58 else 'no')

def strlan():
	for _ in range(int(input())):
		(l, plan) = map(int, input().split())
		c = 0
		for i in input():
			if i == '*':
				c += 1
			else:
				c = 0
			if c == plan:
				print('yes')
				break
		else:
			print('no')

def maxpip():
	for _ in range(int(input())):
		dies = int(input())
		if dies <= 4:
			print(dies * 20)
		if dies <= 12:
			avg = dies // 4
			leftover = dies % 4
			s = 4 - leftover
			if not avg:
				print(leftover * 20)
			elif avg == 1:
				print(leftover * 36 + s * 20)
			elif avg == 2:
				print(leftover * 51 + s * 36)
			else:
				print(s * 51)
		else:
			ans = 51 * 3
			dies -= 9
			layers = dies // 4
			left = dies % 4
			ans += layers * 44
			if not left:
				print(ans + 4 * 3)
			elif left == 1:
				print(ans + 20 + 3 * 3)
			elif left == 2:
				print(ans + 36 + 2 * 3)
			else:
				print(ans + 51 + 1 * 3)

def dies():

	def c(num):
		if not num:
			return 0
		if num == 1:
			return 20
		return 51 if num == 3 else 36
	for i in range(int(input())):
		dice = int(input())
		layers = dice // 4
		left = dice % 4
		calc = (4 - left) * 4
		if layers:
			addon = 0
		else:
			addon = -calc
		print(layers * 44 + c(left) + addon + calc)

def binarystr():
	for _ in range(int(input())):
		s = input()
		lens = len(s)
		num = 0
		while True:
			s1 = bin(num)[2:]
			lens1 = len(s1)
			pos = 0
			pos1 = 0
			while pos < lens and pos1 < lens1:
				if s1[pos1] == s[pos]:
					pos1 += 1
				pos += 1
			if pos1 != lens1:
				break
			num += 1
		print(s1, num)
from itertools import repeat

def worthymatix():
	for _ in range(int(input())):
		(rows, cols, avgnum) = map(int, input().split())
		l = [[int(i) - avgnum for i in input().split()] for _ in repeat(None, rows)]
		ans = 0
		for i in range(rows):
			for i1 in range(cols):
				if l[i][i1] >= 0:
					s = 0
					c = 0
					limit = min(i, i1)
					while c <= limit:
						start = i1 - c
						for up in range(i, i - c - 1, -1):
							s += l[up][start]
						s += sum(l[i - c][i1 - c + 1:i1 + 1])
						if s < 0:
							break
						c += 1
						ans += 1
		print(ans)

def worthymatrix():

	def decide(x, y, l):
		now = prefix[x + l - 1][y + l - 1]
		if x:
			now -= prefix[x - 1][y + l - 1]
		if y:
			now -= prefix[x + l - 1][y - 1]
		if x and y:
			now += prefix[x - 1][y - 1]
		return now / (l * l) >= avgnum
	for _ in range(int(input())):
		(rows, cols, avgnum) = map(int, input().split())
		prefix = [[0] * cols for _ in range(rows)]
		for i in range(rows):
			s = input().split()
			for i1 in range(cols):
				now = 0
				if i1:
					now += prefix[i][i1 - 1]
				if i:
					now += prefix[i - 1][i1]
				now += int(s[i1])
				if i and i1:
					now -= prefix[i - 1][i1 - 1]
				prefix[i][i1] = now
		ans = 0
		for i in range(rows):
			for i1 in range(cols):
				mar = min(rows - i, cols - i1)
				(l, r) = (0, mar + 1)
				while l < r - 1:
					m = (l + r) // 2
					if decide(i, i1, m):
						r = m
					else:
						l = m
				ans += mar - r + 1
		print(ans)

def binarystrmex():
	for _ in range(int(input())):
		s = input().rstrip()
		lens = len(s)
		next0 = [0] * lens
		next1 = next0[:]
		n0 = float('inf')
		n1 = n0
		one = False
		zero = False
		c = 0
		countl = next1[:]
		for i in range(lens - 1, -1, -1):
			next0[i] = n0
			next1[i] = n1
			countl[i] = c
			if s[i] == '1':
				n1 = i
				one = True
			else:
				n0 = i
				zero = True
			if one and zero:
				zero = one = False
				c += 1
		inf = float('inf')
		if n0 == inf:
			print('0')
			continue
		if n1 == inf:
			print('1')
			continue
		curr = n1
		ans = ['1']
		while True:
			(pos0, pos1) = (next0[curr], next1[curr])
			if pos0 == inf:
				ans.append('0')
				break
			if pos1 == inf:
				ans.append('1')
				break
			if countl[pos0] <= countl[pos1]:
				ans.append('0')
				curr = pos0
			else:
				ans.append('1')
				curr = pos1
		print(''.join(ans))
binarystrmex()


T = int(input())
for _ in range(T):
	S = input()
	n = len(S)
	lenA = [0 for _ in range(n)]
	count = 0
	one = zero = False
	for i in range(n - 1, -1, -1):
		lenA[i] = count
		if S[i] == '0':
			zero = True
		else:
			one = True
		if one and zero:
			count += 1
			one = zero = False
	next1A = [None] * n
	next0A = [None] * n
	one = zero = None
	for i in range(n - 1, -1, -1):
		next1A[i] = one
		next0A[i] = zero
		if S[i] == '0':
			zero = i
		else:
			one = i
	if one == None:
		print(1)
	elif zero == None:
		print(0)
	else:
		ans = ['1']
		i = one
		while True:
			if next0A[i] == None:
				ans.append('0')
				break
			elif next1A[i] == None:
				ans.append('1')
				break
			if lenA[next1A[i]] >= lenA[next0A[i]]:
				i = next0A[i]
				ans.append('0')
			else:
				i = next1A[i]
				ans.append('1')
		print(''.join(ans))


import math
try:
	t = int(input())
	while t:
		t -= 1
		s = input()
		n = len(s)
		l = [0] * n
		c = 0
		next0 = [0] * n
		next1 = [0] * n
		(n0, n1) = (n, n)
		for i in range(n - 1, -1, -1):
			next0[i] = n0
			next1[i] = n1
			if s[i] == '1':
				n1 = i
			else:
				n0 = i
		if n0 == n:
			print(0)
			continue
		elif n1 == n:
			print(1)
			continue
		z = False
		o = False
		i = n - 1
		while i > 0:
			if s[i] == s[i - 1]:
				l[i - 1] = c
			else:
				l[i - 1] = c
				i -= 1
				c += 1
				if i - 1 >= 0:
					l[i - 1] = c
			i -= 1
		curr = n1
		ans = ''
		one = 0
		zero = 0
		while 1:
			ans += s[curr]
			(one, zero) = (next1[curr], next0[curr])
			if zero == n:
				ans += '0'
				break
			if one == n:
				ans += '1'
				break
			if l[one] >= l[zero]:
				curr = zero
			else:
				curr = one
		print(ans)
except:
	pass


def get_indices(l, i):
	n = len(l)
	(x, y) = (-1, -1)
	while i < n:
		if l[i] == '0' and x == -1:
			x = i
		if l[i] == '1' and y == -1:
			y = i
		if x != -1 and y != -1:
			return (x, y)
		i += 1
	if x == -1:
		return (i, y)
	if y == -1:
		return (x, i)

def solve2():
	s = input()
	n = len(s)
	cnt = list()
	one = zero = False
	ans = 0
	(ones, zeros) = (0, 0)
	for i in range(n - 1, -1, -1):
		if one and zero:
			ans += 1
			cnt.append(ans)
			one = zero = False
		else:
			cnt.append(ans)
		if s[i] == '1':
			one = True
			ones += 1
		else:
			zero = True
			zeros += 1
	if cnt[0] == 0:
		if zeros == 0:
			return zeros
		if ones == 0:
			return 1
	cnt.reverse()
	ret = '1'
	i = 0
	while i < n and s[i] != '1':
		i += 1
	while i < n:
		(a, b) = get_indices(s, i + 1)
		if a == n:
			ret += '0'
			break
		if b == n:
			ret += '1'
			break
		if cnt[a] <= cnt[b]:
			ret += '0'
			i = a
		else:
			ret += '1'
			i = b
	return ret
for i in range(int(input())):
	print(solve2())


n1 = int(input())
for i in range(n1):
	s = input()
	if '0' not in s:
		print(0)
	elif '1' not in s:
		print(1)
	else:
		n = len(s)
		l = [0] * n
		cnt = 0
		one = False
		zero = False
		for j in range(n - 1, -1, -1):
			l[j] = cnt
			if s[j] == '1':
				one = True
			if s[j] == '0':
				zero = True
			if one and zero:
				cnt += 1
				zero = False
				one = False
		p = s.find('1')
		f = ''
		while True:
			f += s[p]
			p0 = s.find('0', p + 1)
			p1 = s.find('1', p + 1)
			if p0 == -1:
				f += '0'
				break
			if p1 == -1:
				f += '1'
				break
			if l[p0] <= l[p1]:
				p = p0
			else:
				p = p1
		print(f)


t = int(input())
for _ in range(t):
	s = input()
	if s.count('0') == 0:
		print(0)
	elif s.count('1') == 0:
		print(1)
	else:
		n = len(s)
		l = [0] * n
		cnt = 0
		one = 0
		zero = 0
		for i in range(n - 1, -1, -1):
			l[i] = cnt
			if s[i] == '1':
				one = 1
			if s[i] == '0':
				zero = 1
			if zero and one:
				cnt += 1
				one = 0
				zero = 0
		s1 = ''
		ind = 0
		for i in range(n):
			if s[i] == '1':
				s1 += '1'
				ind = i
				break
		zero = 0
		one = 0
		a1 = b1 = 0
		a2 = b2 = 0
		i = ind + 1
		while i < n:
			if zero == 0 and s[i] == '0':
				zero = 1
				a1 = i
				b1 = l[i]
			if one == 0 and s[i] == '1':
				one = 1
				a2 = i
				b2 = l[i]
			if one and zero:
				if b1 < b2:
					s1 += '0'
					i = a1 + 1
				elif b1 > b2:
					s1 += '1'
					i = a2 + 1
				else:
					s1 += '0'
					i += 1
				one = 0
				zero = 0
			else:
				i += 1
		if one == 0 and zero == 1:
			s1 += '1'
		elif zero == 0 and one == 1:
			s1 += '0'
		else:
			s1 += '0'
		print(s1)


T = int(input())
maxn = 10 ** 6 + 2
for _ in range(T):
	S = input()
	N = len(S)
	next0 = [N for i in range(N)]
	next1 = [N for i in range(N)]
	n0 = maxn
	n1 = maxn
	for i in range(N - 1, -1, -1):
		next0[i] = n0
		next1[i] = n1
		if S[i] == '1':
			n1 = i
		else:
			n0 = i
	if n0 == maxn:
		print(0)
		continue
	if n1 == maxn:
		print(1)
		continue
	(zero, one) = (False, False)
	count = 0
	length = [''] * N
	for i in range(N - 1, -1, -1):
		length[i] = count
		if S[i] == '0':
			zero = True
		if S[i] == '1':
			one = True
		if one and zero:
			count += 1
			(zero, one) = (False, False)
	ans = ''
	curr = n1
	while 1:
		ans += S[curr]
		(p1, p0) = (next1[curr], next0[curr])
		if p0 == maxn:
			ans += '0'
			break
		if p1 == maxn:
			ans += '1'
			break
		if length[p0] <= length[p1]:
			curr = p0
		else:
			curr = p1
	print(ans)


import sys
inf = float('inf')

def solve(s):
	n = len(s)
	next1 = [inf] * n
	next0 = [inf] * n
	n0 = inf
	n1 = inf
	for i in range(n - 1, -1, -1):
		next1[i] = n1
		next0[i] = n0
		if s[i] == '1':
			n1 = i
		else:
			n0 = i
	if n0 == inf:
		return '0'
	if n1 == inf:
		return '1'
	one = zero = False
	dp = [0] * n
	count = 0
	for i in range(n - 1, -1, -1):
		dp[i] = count
		if s[i] == '1':
			one = True
		if s[i] == '0':
			zero = True
		if one and zero:
			count += 1
			one = zero = False
	res = ''
	curr = n1
	while True:
		res += s[curr]
		p0 = next0[curr]
		p1 = next1[curr]
		if p0 == inf:
			res += '0'
			break
		if p1 == inf:
			res += '1'
			break
		if dp[p0] <= dp[p1]:
			curr = p0
		else:
			curr = p1
	return res
T = int(input())
for _ in range(T):
	s = input()
	print(solve(s))


import sys
for _ in range(int(input())):
	s = input()
	n = len(s)
	next0 = [n] * n
	next1 = [n] * n
	(n0, n1) = (n, n)
	for i in range(n - 1, -1, -1):
		next0[i] = n0
		next1[i] = n1
		if s[i] == '1':
			n1 = i
		else:
			n0 = i
	length = [0] * n
	(zero, one) = (False, False)
	cnt = 0
	if n0 == n:
		print('0')
		continue
	if n1 == n:
		print('1')
		continue
	for i in range(n - 1, -1, -1):
		if s[i] == '0':
			zero = True
		if s[i] == '1':
			one = True
		length[i] = cnt
		if one and zero:
			cnt += 1
			(zero, one) = (False, False)
	ans = ''
	curr = n1
	while True:
		ans += s[curr]
		(p0, p1) = (next0[curr], next1[curr])
		if p0 == n:
			ans += '0'
			break
		if p1 == n:
			ans += '1'
			break
		if length[p0] <= length[p1]:
			curr = p0
		else:
			curr = p1
	print(ans)


import sys
input_ = lambda : sys.stdin.readline().strip('\r\n')
t = int(input_())
for _ in range(t):
	s = input_()
	n = len(s)
	inf = n
	n0 = inf
	n1 = inf
	next0 = [0] * n
	next1 = [0] * n
	for i in range(n - 1, -1, -1):
		next0[i] = n0
		next1[i] = n1
		if s[i] == '1':
			n1 = i
		else:
			n0 = i
	if n1 == inf:
		print('1')
		continue
	if n0 == inf:
		print('0')
		continue
	length = [0] * n
	one = False
	two = False
	cnt = 0
	for i in range(n - 1, -1, -1):
		length[i] = cnt
		if s[i] == '1':
			one = True
		else:
			two = True
		if one and two:
			cnt += 1
			(one, two) = (False, False)
	ans = ''
	cur = n1
	while True:
		ans += s[cur]
		(p0, p1) = (next0[cur], next1[cur])
		if p0 == n:
			ans += '0'
			break
		if p1 == n:
			ans += '1'
			break
		if length[p0] <= length[p1]:
			cur = p0
		else:
			cur = p1
	print(ans)


import sys
inf = sys.maxsize
for _ in range(int(input())):
	s = input()
	n = len(s)
	next0 = [inf] * n
	next1 = [inf] * n
	(n0, n1) = (inf, inf)
	for i in range(n - 1, -1, -1):
		next0[i] = n0
		next1[i] = n1
		if s[i] == '0':
			n0 = i
		else:
			n1 = i
	if n0 == inf:
		print('0')
		continue
	if n1 == inf:
		print('1')
		continue
	ln = [0] * n
	one = zero = False
	count = 0
	for i in range(n - 1, -1, -1):
		ln[i] = count
		if s[i] == '0':
			zero = True
		if s[i] == '1':
			one = True
		if zero and one:
			count += 1
			zero = one = False
	ans = ''
	curr = n1
	while True:
		ans += s[curr]
		p0 = next0[curr]
		p1 = next1[curr]
		if p0 == inf:
			ans += '0'
			break
		if p1 == inf:
			ans += '1'
			break
		if ln[p0] <= ln[p1]:
			curr = p0
		else:
			curr = p1
	print(ans)


def solve(s):
	n = len(s)
	next0 = [mx] * n
	next1 = [mx] * n
	(n0, n1) = (mx, mx)
	for i in range(n - 1, -1, -1):
		next0[i] = n0
		next1[i] = n1
		if s[i] == '1':
			n1 = i
		else:
			n0 = i
	if n0 == mx:
		return 0
	if n1 == mx:
		return 1
	dplen = [0] * n
	(one, zero) = (False, False)
	count = 0
	for i in range(n - 1, -1, -1):
		dplen[i] = count
		if s[i] == '0':
			zero = True
		if s[i] == '1':
			one = True
		if one and zero:
			count += 1
			(one, zero) = (False, False)
	ans = ''
	curr = n1
	while True:
		ans += s[curr]
		p0 = next0[curr]
		p1 = next1[curr]
		if p0 == mx:
			ans += '0'
			break
		if p1 == mx:
			ans += '1'
			break
		if dplen[p0] <= dplen[p1]:
			curr = p0
		else:
			curr = p1
	return ans
mx = 1000005
for t in range(int(input())):
	s = input()
	print(solve(s))


from collections import Counter
for _ in range(int(input())):
	s = list(input())
	c = Counter(s)
	if c['0'] == 0:
		print(0)
		continue
	n = len(s)
	num0 = [0] * n
	num1 = [0] * n
	last_pos = n
	for i in range(n - 1, -1, -1):
		if s[i] == '0':
			last_pos = i
		num0[i] = last_pos
	last_pos = n
	for i in range(n - 1, -1, -1):
		if s[i] == '1':
			last_pos = i
		num1[i] = last_pos
	dp = [0] * (n + 2)
	dp1 = [0] * (n + 2)
	for i in range(n - 1, -1, -1):
		dp[i] = dp[i + 1]
		if s[i] == '0' and num1[i] < n:
			dp[i] = max(dp[i], dp[num1[i] + 1] + 1)
		if s[i] == '1' and num0[i] < n:
			dp[i] = max(dp[i], dp[num0[i] + 1] + 1)
		dp1[i] = dp1[i + 1]
		if num1[i] < n:
			dp1[i] = max(dp1[i], dp[num1[i] + 1] + 1)
	l = dp1[0] + 1
	x = num1[0] + 1
	ans = ['1']
	for i in range(1, l):
		if x >= n:
			ans.append('0')
			continue
		if num0[x] >= n:
			ans.append('0')
			x = num0[x] + 1
			continue
		if dp[num0[x] + 1] < l - i - 1:
			ans.append('0')
			x = num0[x] + 1
		else:
			ans.append('1')
			x = num1[x] + 1
	print(''.join(ans))


t = int(input())
for _ in range(t):
	s = input()
	dp = [0] * len(s)
	zero = one = False
	flag = 0
	for i in range(len(s) - 1, -1, -1):
		if zero and one:
			zero = one = False
			dp[i] = dp[i + 1] + 1
			flag = 1
		elif flag == 1:
			dp[i] = dp[i + 1]
		if s[i] == '0':
			zero = True
		if s[i] == '1':
			one = True
	next0 = [0] * len(s)
	next1 = [0] * len(s)
	n0 = n1 = float('inf')
	for i in range(len(s) - 1, -1, -1):
		next0[i] = n0
		next1[i] = n1
		if s[i] == '0':
			n0 = i
		if s[i] == '1':
			n1 = i
	if n1 == float('inf'):
		print('1')
		continue
	if n0 == float('inf'):
		print('0')
		continue
	result = '1'
	i = n1
	while True:
		n0 = next0[i]
		n1 = next1[i]
		if n0 == float('inf'):
			result += '0'
			break
		elif n1 == float('inf'):
			result += '1'
			break
		elif dp[n0] <= dp[n1]:
			result += '0'
			i = n0
		else:
			result += '1'
			i = n1
	print(result)


for t in range(int(input())):
	a = input()
	if '0' not in a:
		print(0)
		continue
	if '1' not in a:
		print(1)
		continue
	n = len(a)
	for i in range(n):
		if a[i] == '1':
			a = a[i + 1:]
			break
	if a == '':
		print(10)
		continue
	n = len(a)
	next0 = [-1 for i in range(n)]
	next1 = [-1 for i in range(n)]
	b = [0 for i in range(n)]
	p0 = -1
	p1 = -1
	s = set()
	c = 0
	for i in range(n - 1, -1, -1):
		b[i] = c
		next0[i] = p0
		next1[i] = p1
		if a[i] == '1':
			p1 = i
		else:
			p0 = i
		s.add(a[i])
		if '0' in s and '1' in s:
			c += 1
			s = set()
	ans = '1'
	while 1:
		if p0 == -1:
			ans += '0'
			break
		elif p1 == -1:
			ans += '1'
			break
		if b[p0] <= b[p1]:
			ans += '0'
			p1 = next1[p0]
			p0 = next0[p0]
		else:
			ans += '1'
			p0 = next0[p1]
			p1 = next1[p1]
	print(ans)


import io, os

def get_result_bound_length(main_string):
	current_pattern = main_string[-1:]
	pattern_list = []
	pattern_count = 0
	for i in range(len(main_string) - 1, -1, -1):
		pattern_list.append(pattern_count)
		if main_string[i] != current_pattern:
			pattern_count += 1
			if i > 0:
				current_pattern = main_string[i - 1]
	pattern_list.append(pattern_count)
	pattern_list.reverse()
	return pattern_list

def is_subsequence(main_string, test_string):
	i = 0
	for j in range(len(main_string)):
		if test_string[i] == main_string[j]:
			i += 1
		if i == len(test_string):
			return True
	if i == len(test_string):
		return True
	else:
		return False
rearBit0 = [0 for _ in range(pow(10, 6) + 10)]
rearBit1 = [0 for _ in range(pow(10, 6) + 10)]
for _ in range(int(input())):
	superArray = []
	mex = ''
	lastIdx = -1
	binaryString = input()
	stringLen = len(binaryString)
	for i in range(stringLen):
		if binaryString[i] == '0':
			for j in range(lastIdx + 1, i + 1):
				rearBit0[j] = i
			lastIdx = i
	for i in range(lastIdx + 1, stringLen + 3):
		rearBit0[i] = stringLen
	if rearBit0[0] == stringLen:
		print(0)
		continue
	lastIdx = -1
	for i in range(stringLen):
		if binaryString[i] == '1':
			for j in range(lastIdx + 1, i + 1):
				rearBit1[j] = i
			lastIdx = i
	for i in range(lastIdx + 1, stringLen + 3):
		rearBit1[i] = stringLen
	superArray = get_result_bound_length(binaryString)
	n = len(superArray)
	for i in range(n, n + 4):
		superArray.append(0)
	length = superArray[0] + 1
	currIdx = rearBit1[0] + 1
	mex += '1'
	for i in range(1, length):
		if currIdx >= stringLen:
			mex += '0'
			continue
		if rearBit0[currIdx] >= stringLen:
			mex += '0'
			currIdx = rearBit0[currIdx] + 1
			continue
		if superArray[rearBit0[currIdx] + 1] < length - i - 1:
			mex += '0'
			currIdx = rearBit0[currIdx] + 1
		else:
			mex += '1'
			currIdx = rearBit1[currIdx] + 1
	if not is_subsequence(binaryString, mex):
		print(mex)
		continue
	else:
		mex = ''
		length = superArray[0] + 2
		currIdx = rearBit1[0] + 1
		mex += '1'
		for i in range(1, length):
			if rearBit0[currIdx] >= stringLen:
				mex += '0'
				currIdx = rearBit0[currIdx] + 1
				continue
			if currIdx >= stringLen:
				mex += '0'
				continue
			if superArray[rearBit0[currIdx] + 1] < length - i - 1:
				mex += '0'
				currIdx = rearBit0[currIdx] + 1
			else:
				mex += '1'
				currIdx = rearBit1[currIdx] + 1
		if not is_subsequence(binaryString, mex):
			print(mex)
			continue
		else:
			mex = ''
			length = superArray[0] + 3
			currIdx = rearBit1[0] + 1
			mex += '1'
			for i in range(1, length):
				if rearBit0[currIdx] >= stringLen:
					mex += '0'
					currIdx = rearBit0[currIdx] + 1
					continue
				if currIdx >= stringLen:
					mex += '0'
					continue
				if superArray[rearBit0[currIdx] + 1] < length - i - 1:
					mex += '0'
					currIdx = rearBit0[currIdx] + 1
				else:
					mex += '1'
					currIdx = rearBit1[currIdx] + 1
			if not is_subsequence(binaryString, mex):
				print(mex)
				continue


(list1, list2, list3, list4) = ([''] * (10 ** 6 + 2), [''] * (10 ** 6 + 2), [''] * 10 ** 6, [''] * 10 ** 6)

def abc(n, x):
	l = -1
	for i in range(x):
		if n[i] == '0':
			for j in range(l + 1, i + 1):
				list3[j] = i
			l = i
	for i in range(l + 1, x):
		list3[i] = x
	if list3[0] == x:
		return 0
	l = -1
	for i in range(x):
		if n[i] == '1':
			for j in range(l + 1, i + 1):
				list4[j] = i
			l = i
	for i in range(l + 1, x):
		list4[i] = x
	list1[x] = 0
	list1[x + 1] = 0
	list2[x] = 0
	list2[x + 1] = 0
	for i in range(x - 1, -1, -1):
		list1[i] = list1[i + 1]
		if n[i] == '0' and list4[i] < x:
			list1[i] = max(list1[i], list1[list4[i] + 1] + 1)
		if n[i] == '1' and list3[i] < x:
			list1[i] = max(list1[i], list1[list3[i] + 1] + 1)
		list2[i] = list1[i + 1]
		if list4[i] < x:
			list2[i] = max(list2[i], list1[list4[i] + 1] + 1)
	var2 = list2[0] + 1
	var3 = list4[0] + 1
	sol = '1'
	for i in range(1, var2):
		if var3 >= x:
			sol += '0'
			continue
		if list3[var3] >= x:
			sol += '0'
			var3 = list3[var3] + 1
			continue
		if list1[list3[var3] + 1] < var2 - i - 1:
			sol += '0'
			var3 = list3[var3] + 1
		else:
			sol += '1'
			var3 = list4[var3] + 1
	return sol
for _ in range(int(input())):
	n = input()
	x = len(n)
	if x <= 10:
		i = 0
		while i < 1000000:
			x = bin(i).replace('0b', '')
			(j, k) = (0, 0)
			c = 0
			while j < len(n) and k < len(x):
				if n[j] == x[k]:
					j += 1
					k += 1
					c += 1
				else:
					j += 1
			i += 1
			if c != len(x):
				print(x)
				break
	else:
		print(abc(n, x))


MAX = 10 ** 6
zero = [0] * MAX
ones = [0] * MAX
change = [0] * (MAX + 2)
group = [0] * (MAX + 2)

def solve():
	s = input()
	l = len(s)
	(i0, i1, j) = (0, 0, 0)
	for bit in s:
		if int(bit):
			for k in range(i1, j + 1):
				ones[k] = j
			i1 = j + 1
		else:
			for k in range(i0, j + 1):
				zero[k] = j
			i0 = j + 1
		j += 1
	for k in range(i0, l):
		zero[k] = l
	if zero[0] == l:
		print(0)
		return
	for k in range(i1, l):
		ones[k] = l
	(change[l], change[l + 1], group[l], group[l + 1]) = (0, 0, 0, 0)
	for k in range(l - 1, -1, -1):
		change[k] = change[k + 1]
		if int(s[k]) and zero[k] < l:
			change[k] = max(change[k], change[zero[k] + 1] + 1)
		elif not int(s[k]) and ones[k] < l:
			change[k] = max(change[k], change[ones[k] + 1] + 1)
		group[k] = group[k + 1]
		if ones[k] < l:
			group[k] = max(group[k], change[ones[k] + 1] + 1)
	l2 = group[0] + 1
	curr = ones[0] + 1
	mex = '1'
	for k in range(1, l2):
		if curr >= l:
			mex += '0'
		elif change[zero[curr] + 1] < l2 - k - 1 or zero[curr] >= l:
			mex += '0'
			curr = zero[curr] + 1
		else:
			mex += '1'
			curr = ones[curr] + 1
	print(mex)
for _ in range(int(input())):
	solve()


(list1, list2, list3, list4) = ([''] * (10 ** 6 + 2), [''] * (10 ** 6 + 2), [''] * 10 ** 6, [''] * 10 ** 6)

def abc(n, x):
	l = -1
	for i in range(x):
		if n[i] == '0':
			for j in range(l + 1, i + 1):
				list3[j] = i
			l = i
	for i in range(l + 1, x):
		list3[i] = x
	if list3[0] == x:
		return 0
	l = -1
	for i in range(x):
		if n[i] == '1':
			for j in range(l + 1, i + 1):
				list4[j] = i
			l = i
	for i in range(l + 1, x):
		list4[i] = x
	list1[x] = 0
	list1[x + 1] = 0
	list2[x] = 0
	list2[x + 1] = 0
	for i in range(x - 1, -1, -1):
		list1[i] = list1[i + 1]
		if n[i] == '0' and list4[i] < x:
			list1[i] = max(list1[i], list1[list4[i] + 1] + 1)
		if n[i] == '1' and list3[i] < x:
			list1[i] = max(list1[i], list1[list3[i] + 1] + 1)
		list2[i] = list1[i + 1]
		if list4[i] < x:
			list2[i] = max(list2[i], list1[list4[i] + 1] + 1)
	var2 = list2[0] + 1
	var3 = list4[0] + 1
	sol = '1'
	for i in range(1, var2):
		if var3 >= x:
			sol += '0'
			continue
		if list3[var3] >= x:
			sol += '0'
			var3 = list3[var3] + 1
			continue
		if list1[list3[var3] + 1] < var2 - i - 1:
			sol += '0'
			var3 = list3[var3] + 1
		else:
			sol += '1'
			var3 = list4[var3] + 1
	return sol
for _ in range(int(input())):
	n = input()
	x = len(n)
	print(abc(n, x))


t = int(input())
for _ in range(t):
	s = input()
	first1 = s.find('1')
	first0 = s.find('0')
	n = len(s)
	if first1 == -1:
		print('1')
		continue
	if first0 == -1:
		print('0')
		continue
	zeros = [0] * n
	ones = [0] * n
	ind0 = n
	ind1 = n
	for i in range(n - 1, first1 - 1, -1):
		zeros[i] = ind0
		ones[i] = ind1
		if s[i] == '0':
			ind0 = i
		else:
			ind1 = i
	s += '0'
	s = list(s)
	dplen = [1111111] * (n + 1)
	dpind = [0] * (n + 1)
	dplen[first1] = 1
	dpind[first1] = -1
	for i in range(first1, n):
		next0 = zeros[i]
		next1 = ones[i]
		if dplen[next0] > dplen[i] + 1:
			dplen[next0] = dplen[i] + 1
			dpind[next0] = i
			if next0 == n:
				s[n] = '0'
		elif dplen[next0] == dplen[i] + 1:
			if s[i] == '0' and s[dpind[next0]] == '1':
				dpind[next0] = i
			if next0 == n:
				s[n] = '0'
		if dplen[next1] > dplen[i] + 1:
			dplen[next1] = dplen[i] + 1
			dpind[next1] = i
			if next1 == n:
				s[n] = '1'
		elif dplen[next1] == dplen[i] + 1:
			if s[i] == '0' and s[dpind[next1]] == '1':
				dpind[next1] = i
	ans = ''
	ans += s[n]
	index = dpind[n]
	while index != -1:
		ans = s[index] + ans
		index = dpind[index]
	print(ans)


test = int(input())
while test:
	s = input()
	length = len(s)
	next0 = [0] * length
	next1 = [0] * length
	last_pos = -1
	for i in range(length):
		if s[i] == '0':
			for j in range(last_pos + 1, i + 1):
				next0[j] = i
				last_pos = i
	for i in range(last_pos + 1, length):
		next0[i] = length
	if next0[0] == length:
		print(0)
	else:
		last_pos = -1
		for i in range(length):
			if s[i] == '1':
				for j in range(last_pos + 1, i + 1):
					next1[j] = i
					last_pos = i
		for i in range(last_pos + 1, length):
			next1[i] = length
		dp = [0] * (length + 1)
		dp1 = [0] * (length + 1)
		for i in range(length - 1, -1, -1):
			dp[i] = dp[i + 1]
			if s[i] == '0' and next1[i] < length:
				dp[i] = max(dp[i], dp[next1[i] + 1] + 1)
			if s[i] == '1' and next0[i] < length:
				dp[i] = max(dp[i], dp[next0[i] + 1] + 1)
			dp1[i] = dp[i + 1]
			if next1[i] < length:
				dp1[i] = max(dp1[i], dp[next1[i] + 1] + 1)
		length1 = dp1[0] + 1
		curind = next1[0] + 1
		ans = '1'
		for i in range(1, length1):
			if curind >= length:
				ans += '0'
				continue
			if next0[curind] >= length:
				ans += '0'
				curind = next0[curind] + 1
				continue
			if dp[next0[curind] + 1] < length1 - i - 1:
				ans += '0'
				curind = next0[curind] + 1
			else:
				ans += '1'
				curind = next1[curind] + 1
		print(ans)
	test -= 1


for _ in range(int(input())):
	s = input()
	n = len(s)
	(c0, c1) = ([n] * n, [n] * n)
	(dp0, dp1) = ([0] * (n + 2), [0] * (n + 2))
	pos0 = -1
	pos1 = -1
	for i in range(n):
		if s[i] == '0':
			for j in range(pos0 + 1, i + 1):
				c0[j] = i
			pos0 = i
		else:
			for j in range(pos1 + 1, i + 1):
				c1[j] = i
			pos1 = i
	if c0[0] == n:
		print('0')
	else:
		for i in range(n - 1, -1, -1):
			dp0[i] = dp0[i + 1]
			if s[i] == '0' and c1[i] < n:
				dp0[i] = max(dp0[i], dp0[c1[i] + 1] + 1)
			if s[i] == '1' and c0[i] < n:
				dp0[i] = max(dp0[i], dp0[c0[i] + 1] + 1)
			dp1[i] = dp1[i + 1]
			if c1[i] < n:
				dp1[i] = max(dp1[i], dp0[c1[i] + 1] + 1)
		res = '1'
		bits = dp1[0] + 1
		c = c1[0] + 1
		for i in range(1, bits):
			if c >= n:
				res += '0'
			elif c0[c] >= n:
				res += '0'
				c = c0[c] + 1
			elif dp0[c0[c] + 1] < bits - i - 1:
				res += '0'
				c = c0[c] + 1
			else:
				res += '1'
				c = c1[c] + 1
		print(res)


for t in range(int(input())):
	s = input()
	if '0' not in s:
		print('0')
		continue
	n = len(s)
	(a, b) = ([0] * n, [0] * n)
	(c0, c1) = (n, n)
	for i in range(n - 1, -1, -1):
		if s[i] == '0':
			c0 = i
		else:
			c1 = i
		a[i] = c0
		b[i] = c1
	(dp0, dp1) = ([0] * (n + 1), [0] * (n + 1))
	for i in range(n - 1, -1, -1):
		dp0[i] = dp0[i + 1]
		if s[i] == '0' and b[i] < n:
			dp0[i] = max(dp0[i], dp0[b[i] + 1] + 1)
		if s[i] == '1' and a[i] < n:
			dp0[i] = max(dp0[i], dp0[a[i] + 1] + 1)
		dp1[i] = dp1[i + 1]
		if b[i] < n:
			dp1[i] = max(dp1[i], dp0[b[i] + 1] + 1)
	(l, x) = (dp1[0] + 1, b[0] + 1)
	res = '1'
	for i in range(1, l):
		if x >= n:
			res += '0'
		elif a[x] >= n:
			res += '0'
			x = a[x] + 1
		elif dp0[a[x] + 1] < l - i - 1:
			res += '0'
			x = a[x] + 1
		else:
			res += '1'
			x = b[x] + 1
	print(res)


import math

def solve():
	s = input()
	n = len(s)
	mx = n + 2
	arr0 = [0 for i in range(mx)]
	arr1 = [0 for i in range(mx)]
	result0 = [0 for i in range(mx + 2)]
	result1 = [0 for i in range(mx + 2)]
	ind = -1
	for i in range(n):
		if s[i] == '0':
			for j in range(ind + 1, i + 1):
				arr0[j] = i
			ind = i
	for i in range(ind + 1, n):
		arr0[i] = n
	if arr0[0] == n:
		print(0)
		return
	ind = -1
	for i in range(n):
		if s[i] == '1':
			for j in range(ind + 1, i + 1):
				arr1[j] = i
			ind = i
	for i in range(ind + 1, n):
		arr1[i] = n
	for i in range(n - 1, -1, -1):
		result0[i] = result0[i + 1]
		if s[i] == '0' and arr1[i] < n:
			result0[i] = max(result0[i], result0[arr1[i] + 1] + 1)
		if s[i] == '1' and arr0[i] < n:
			result0[i] = max(result0[i], result0[arr0[i] + 1] + 1)
		result1[i] = result1[i + 1]
		if arr1[i] < n:
			result1[i] = max(result1[i], result0[arr1[i] + 1] + 1)
	x = result1[0] + 1
	count = arr1[0] + 1
	ans = '1'
	for i in range(1, x):
		if count >= n:
			ans += '0'
			continue
		if arr0[count] >= n:
			ans += '0'
			count = arr0[count] + 1
			continue
		if result0[arr0[count] + 1] < x - i - 1:
			ans += '0'
			count = arr0[count] + 1
		else:
			ans += '1'
			count = arr1[count] + 1
	print(ans)

def inp():
	return int(input())

def inl():
	return [int(i) for i in input().split()]
t = 1
t = inp()
while t:
	solve()
	t -= 1


n0 = [-1] * 10000000
n1 = [-1] * 10000000
arr = [-1] * 10000000
arr1 = [-1] * 10000000
for _ in range(int(input())):
	s = input()
	l = len(s)
	lp = -1
	for i in range(0, l):
		if s[i] == '0':
			for j in range(lp + 1, i + 1):
				n0[j] = i
			lp = i
	for i in range(lp + 1, l):
		n0[i] = l
	if n0[0] == l:
		print(0)
		continue
	lp = -1
	for i in range(0, l):
		if s[i] == '1':
			for j in range(lp + 1, i + 1):
				n1[j] = i
			lp = i
	for i in range(lp + 1, l):
		n1[i] = l
	arr[l + 1] = 0
	arr[l] = 0
	arr1[l + 1] = 0
	arr1[l] = 0
	i = l - 1
	while i >= 0:
		arr[i] = arr[i + 1]
		if s[i] == '0' and n1[i] < l:
			arr[i] = max(arr[i], arr[n1[i] + 1] + 1)
		if s[i] == '1' and n0[i] < l:
			arr[i] = max(arr[i], arr[n0[i] + 1] + 1)
		arr1[i] = arr1[i + 1]
		if n1[i] < l:
			arr1[i] = max(arr1[i], arr[n1[i] + 1] + 1)
		i -= 1
	ans = '1'
	curr = n1[0] + 1
	le = arr1[0] + 1
	for i in range(1, le):
		if curr >= l:
			ans += '0'
			continue
		if n0[curr] >= l:
			ans += '0'
			curr = n0[curr] + 1
			continue
		if arr[n0[curr] + 1] < le - i - 1:
			ans += '0'
			curr = n0[curr] + 1
		else:
			ans += '1'
			curr = n1[curr] + 1
	print(ans)


import math
from collections import Counter, defaultdict
readInt = lambda : int(input().strip())
readfloat = lambda : float(input().strip())
intList = lambda : list(map(int, input().strip().split()))
intMap = lambda : map(int, input().strip().split())
floatList = lambda : list(map(float, input().strip().split()))
floatMap = lambda : map(float, input().strip().split())

def solve(string):
	n = len(string)
	zeroes = [0 for i in range(n)]
	ones = [0 for i in range(n)]
	pos = n
	for i in range(n - 1, -1, -1):
		if string[i] == '0':
			pos = i
		zeroes[i] = pos
	pos = n
	for i in range(n - 1, -1, -1):
		if string[i] == '1':
			pos = i
		ones[i] = pos
	zero_len = [0 for i in range(n + 1)]
	one_len = [0 for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		zero_len[i] = zero_len[i + 1]
		if string[i] == '0' and ones[i] < n:
			zero_len[i] = max(zero_len[i], zero_len[ones[i] + 1] + 1)
		if string[i] == '1' and zeroes[i] < n:
			zero_len[i] = max(zero_len[i], zero_len[zeroes[i] + 1] + 1)
		one_len[i] = one_len[i + 1]
		if ones[i] < n:
			one_len[i] = max(one_len[i], zero_len[ones[i] + 1] + 1)
	length = one_len[0] + 1
	x = ones[0] + 1
	res = ['1']
	for i in range(1, length):
		if x >= n:
			res.append('0')
			continue
		if zeroes[x] >= n:
			res.append('0')
			x = zeroes[x] + 1
			continue
		if zero_len[zeroes[x] + 1] < length - i - 1:
			res.append('0')
			x = zeroes[x] + 1
		else:
			res.append('1')
			x = ones[x] + 1
	return ''.join(res)
for _ in range(readInt()):
	string = list(input())
	c = Counter(string)
	if c['0'] == 0:
		print(0)
		continue
	print(solve(string))


def cal(l):
	n = len(l)
	pos = -1
	for i in range(n):
		if l[i] == '0':
			for j in range(pos + 1, i + 1):
				arr1[j] = i
			pos = i
	for i in range(pos + 1, n):
		arr1[i] = n
	if arr1[0] == n:
		return 0
	pos = -1
	for i in range(n):
		if l[i] == '1':
			for j in range(pos + 1, i + 1):
				arr2[j] = i
			pos = i
	for i in range(pos + 1, n):
		arr2[i] = n
	temp1[n] = 0
	temp1[n + 1] = 0
	temp2[n] = 0
	temp2[n + 1] = 0
	for i in range(n - 1, -1, -1):
		temp1[i] = temp1[i + 1]
		if l[i] == '0' and arr2[i] < n:
			temp1[i] = max(temp1[i], temp1[arr2[i] + 1] + 1)
		if l[i] == '1' and arr1[i] < n:
			temp1[i] = max(temp1[i], temp1[arr1[i] + 1] + 1)
		temp2[i] = temp2[i + 1]
		if arr2[i] < n:
			temp2[i] = max(temp2[i], temp1[arr2[i] + 1] + 1)
	x = temp2[0] + 1
	coun = arr2[0] + 1
	ans = '1'
	for i in range(1, x):
		if coun >= n:
			ans += '0'
			continue
		if arr1[coun] >= n:
			ans += '0'
			coun = arr1[coun] + 1
			continue
		if temp1[arr1[coun] + 1] < x - i - 1:
			ans += '0'
			coun = arr1[coun] + 1
		else:
			ans += '1'
			coun = arr2[coun] + 1
	return ans
for _ in range(int(input())):
	t = input()
	maxy = len(t) + 10
	arr1 = [0 for i in range(maxy)]
	arr2 = [0 for i in range(maxy)]
	temp1 = [0 for i in range(maxy + 2)]
	temp2 = [0 for i in range(maxy + 2)]
	print(cal(t))


import itertools
test = int(input())

class dparr:

	def dparrcalc(s, li1, li2, strl):
		mem1 = [0] * (strl + 1)
		mem2 = [0] * (strl + 1)
		for i in range(strl - 1, -1, -1):
			mem1[i] = mem1[i + 1]
			if s[i] == '0' and li2[i] < strl:
				mem1[i] = max(mem1[i], mem1[li2[i] + 1] + 1)
			elif s[i] == '1' and li1[i] < strl:
				mem1[i] = max(mem1[i], mem1[li1[i] + 1] + 1)
			mem2[i] = mem2[i + 1]
			if li2[i] < strl:
				mem2[i] = max(mem2[i], mem1[li2[i] + 1] + 1)
		return (mem1, mem2)

def solve(s):
	arr = '1'
	if '0' not in s:
		print(0)
	else:
		strl = len(s)
		li1 = [0] * strl
		li2 = [0] * strl
		mem1 = [0] * (strl + 1)
		mem2 = [0] * (strl + 1)
		zero = -1
		for i in range(0, strl):
			if s[i] == '0':
				for j in range(zero + 1, i + 1):
					li1[j] = i
				zero = i
		one = -1
		for i in range(0, strl):
			if s[i] == '1':
				for j in range(one + 1, i + 1):
					li2[j] = i
				one = i
		for i in range(zero + 1, strl):
			li1[i] = strl
		for i in range(one + 1, strl):
			li2[i] = strl
		x = dparr
		(mem1, mem2) = x.dparrcalc(s, li1, li2, strl)
		iter = li2[0]
		iter += 1
		for i in range(1, 1 + mem2[0]):
			y = 1 + mem2[0] - i - 1
			if iter >= strl:
				arr += '0'
			elif li1[iter] >= strl:
				arr += '0'
				iter = li1[iter] + 1
			elif mem1[li1[iter] + 1] < y:
				arr += '0'
				iter = li1[iter] + 1
			else:
				arr += '1'
				iter = li2[iter] + 1
		print(arr)
for i in range(0, test):
	s = input()
	solve(s)


test = int(input())

def solve(s):
	arr = '1'
	if '0' not in s:
		print(0)
	else:
		strl = len(s)
		li1 = [0] * strl
		li2 = [0] * strl
		mem1 = [0] * (strl + 1)
		mem2 = [0] * (strl + 1)
		zero = -1
		for i in range(0, strl):
			if s[i] == '0':
				for j in range(zero + 1, i + 1):
					li1[j] = i
				zero = i
		one = -1
		for i in range(0, strl):
			if s[i] == '1':
				for j in range(one + 1, i + 1):
					li2[j] = i
				one = i
		for i in range(zero + 1, strl):
			li1[i] = strl
		for i in range(one + 1, strl):
			li2[i] = strl
		for i in range(strl - 1, -1, -1):
			mem1[i] = mem1[i + 1]
			if s[i] == '0' and li2[i] < strl:
				mem1[i] = max(mem1[i], mem1[li2[i] + 1] + 1)
			elif s[i] == '1' and li1[i] < strl:
				mem1[i] = max(mem1[i], mem1[li1[i] + 1] + 1)
			mem2[i] = mem2[i + 1]
			if li2[i] < strl:
				mem2[i] = max(mem2[i], mem1[li2[i] + 1] + 1)
		iter = li2[0]
		iter += 1
		z = 1 + mem2[0]
		for i in range(1, z):
			y = 1 + mem2[0] - i - 1
			if iter >= strl:
				arr += '0'
			elif li1[iter] >= strl:
				arr += '0'
				iter = li1[iter] + 1
			elif mem1[li1[iter] + 1] < y:
				arr += '0'
				iter = li1[iter] + 1
			else:
				arr += '1'
				iter = li2[iter] + 1
		print(arr)
for i in range(0, test):
	s = input()
	solve(s)


t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	nx0 = [None] * n
	nx1 = [None] * n
	ps1 = -1
	ps0 = -1
	for i in range(n):
		if s[i] == '0':
			for j in range(ps0 + 1, i + 1):
				nx0[j] = i
			ps0 = i
		else:
			for j in range(ps1 + 1, i + 1):
				nx1[j] = i
			ps1 = i
	for i in range(ps0 + 1, n):
		nx0[i] = n
	for i in range(ps1 + 1, n):
		nx1[i] = n
	if nx0[0] == n:
		print(0)
		continue
	st0 = [None] * (n + 2)
	st1 = [None] * (n + 2)
	st0[n] = 0
	st0[n + 1] = 0
	st1[n] = 0
	st1[n + 1] = 0
	for i in range(n - 1, -1, -1):
		st0[i] = st0[i + 1]
		if s[i] == '0':
			if nx1[i] < n:
				st0[i] = max(st0[i], st0[nx1[i] + 1] + 1)
		elif nx0[i] < n:
			st0[i] = max(st0[i], st0[nx0[i] + 1] + 1)
	for i in range(n - 1, -1, -1):
		st1[i] = st1[i + 1]
		if nx1[i] < n:
			st1[i] = max(st1[i], st0[nx1[i] + 1] + 1)
	mx = st1[0] + 1
	cur = nx1[0] + 1
	mis = '1'
	for i in range(1, mx):
		if cur >= n:
			mis += '0'
		elif nx0[cur] >= n:
			mis += '0'
			cur = nx0[cur] + 1
		elif st0[nx0[cur] + 1] < mx - i - 1:
			mis += '0'
			cur = nx0[cur] + 1
		else:
			mis += '1'
			cur = nx1[cur] + 1
	print(mis)


maxn = 10 ** 6
dp = [0] * (maxn + 2)
dp1 = [0] * (maxn + 2)
next0 = [0] * maxn
next1 = [0] * maxn

def spar():
	s = input()
	n = len(s)
	last_pos = -1
	for i in range(0, n):
		if s[i] == '0':
			for j in range(last_pos + 1, i + 1):
				next0[j] = i
			last_pos = i
	for i in range(last_pos + 1, n):
		next0[i] = n
	if next0[0] == n:
		print('0')
		return
	last_pos = -1
	for i in range(0, n):
		if s[i] == '1':
			for j in range(last_pos + 1, i + 1):
				next1[j] = i
			last_pos = i
	for i in range(last_pos + 1, n):
		next1[i] = n
	dp[n] = dp[i + 1] = 0
	dp1[n] = dp1[n + 1] = 0
	for i in range(n - 1, -1, -1):
		dp[i] = dp[i + 1]
		if s[i] == '0' and next1[i] < n:
			dp[i] = max(dp[i], dp[next1[i] + 1] + 1)
		if s[i] == '1' and next0[i] < n:
			dp[i] = max(dp[i], dp[next0[i] + 1] + 1)
		dp1[i] = dp1[i + 1]
		if next1[i] < n:
			dp1[i] = max(dp1[i], dp[next1[i] + 1] + 1)
	le = dp1[0] + 1
	curind = next1[0] + 1
	ans = '1'
	for i in range(1, le):
		if curind >= n:
			ans += '0'
			continue
		if next0[curind] >= n:
			ans += '0'
			curind = next0[curind] + 1
			continue
		if dp[next0[curind] + 1] < le - i - 1:
			ans += '0'
			curind = next0[curind] + 1
		else:
			ans += '1'
			curind = next1[curind] + 1
	print(ans)
for i in range(int(input())):
	spar()


ma = 10 ** 6
(lst1, lst, l1, l2) = ([''] * (ma + 2), [''] * (ma + 2), [''] * ma, [''] * ma)

def ff():
	for i in range(7):
		hh = 999
ff()

def solve():
	s = input()
	n = len(s)
	last = -1
	for i in range(n):
		if s[i] == '0':
			for j in range(last + 1, i + 1):
				l1[j] = i
			last = i
	for i in range(last + 1, n):
		l1[i] = n
	if l1[0] == n:
		print(0)
		return
	last = -1
	for i in range(n):
		if s[i] == '1':
			for j in range(last + 1, i + 1):
				l2[j] = i
			last = i
	for i in range(last + 1, n):
		l2[i] = n
	(lst1[n], lst1[n + 1], lst[n], lst[n + 1]) = (0, 0, 0, 0)
	for i in range(n - 1, -1, -1):
		lst1[i] = lst1[i + 1]
		if s[i] == '0' and l2[i] < n:
			lst1[i] = max(lst1[i], lst1[l2[i] + 1] + 1)
		if s[i] == '1' and l1[i] < n:
			lst1[i] = max(lst1[i], lst1[l1[i] + 1] + 1)
		lst[i] = lst1[i + 1]
		if l2[i] < n:
			lst[i] = max(lst[i], lst1[l2[i] + 1] + 1)
	l = lst[0] + 1
	ind = l2[0] + 1
	ans = '1'
	for i in range(1, l):
		if ind >= n:
			ans += '0'
			continue
		if l1[ind] >= n:
			ans += '0'
			ind = l1[ind] + 1
			continue
		if lst1[l1[ind] + 1] < l - i - 1:
			ans += '0'
			ind = l1[ind] + 1
		else:
			ans += '1'
			ind = l2[ind] + 1
	print(ans)
for _ in range(int(input())):
	solve()


testcase = int(input())
for _ in range(testcase):
	input_string = input()
	length_of_s = len(input_string)
	n1 = []
	n2 = []
	DP1 = [0, 0]
	DP2 = [0, 0]
	previous_1 = 0
	previous_2 = 0
	for i in range(length_of_s):
		if input_string[i] == '0':
			for j in range(previous_1, i + 1):
				n1.append(i)
				DP1.append(0)
				previous_1 = i + 1
		elif input_string[i] == '1':
			for k in range(previous_2, i + 1):
				n2.append(i)
				DP2.append(0)
				previous_2 = i + 1
	if len(n1) == 0:
		print(0)
		continue
	if len(n2) == 0:
		print(1)
		continue
	if len(n1) > len(n2):
		for i in range(len(n2), len(n1)):
			n2.append(length_of_s)
			DP2.append(0)
	elif len(n1) < len(n2):
		for i in range(len(n1), len(n2)):
			n1.append(length_of_s)
			DP1.append(0)
	for i in reversed(range(length_of_s)):
		DP1[i] = DP1[i + 1]
		if input_string[i] == '0' and n2[i] < length_of_s:
			DP1[i] = max(DP1[i], DP1[n2[i] + 1] + 1)
		if input_string[i] == '1' and n1[i] < length_of_s:
			DP1[i] = max(DP1[i], DP1[n1[i] + 1] + 1)
		DP2[i] = DP2[i + 1]
		if n2[i] < length_of_s:
			DP2[i] = max(DP2[i], DP1[n2[i] + 1] + 1)
	L = DP2[0] + 1
	X = n2[0] + 1
	answer = '1'
	for i in range(1, L):
		if X >= length_of_s:
			answer += '0'
			continue
		if n1[X] >= length_of_s:
			answer += '0'
			X = n1[X] + 1
			continue
		if DP1[n1[X] + 1] < L - i - 1:
			answer += '0'
			X = n1[X] + 1
		else:
			answer += '1'
			X = n2[X] + 1
	print(answer)


MAXN = 1000000
dp = [0] * (MAXN + 2)
dp1 = [0] * (MAXN + 2)
next0 = [0] * MAXN
next1 = [0] * MAXN

def solve():
	s = input()
	n = len(s)
	last_pos = -1
	for i in range(n):
		if s[i] == '0':
			for j in range(last_pos + 1, i + 1):
				next0[j] = i
				last_pos = i
	for i in range(last_pos + 1, n):
		next0[i] = n
	if next0[0] == n:
		print('0')
		return
	last_pos = -1
	for i in range(n):
		if s[i] == '1':
			for j in range(last_pos + 1, i + 1):
				next1[j] = i
				last_pos = i
	for i in range(last_pos + 1, n):
		next1[i] = n
	dp[n] = dp[n + 1] = 0
	dp1[n] = dp[n + 1] = 0
	for i in range(n - 1, -1, -1):
		dp[i] = dp[i + 1]
		if s[i] == '0' and next1[i] < n:
			dp[i] = max(dp[i], dp[next1[i] + 1] + 1)
		if s[i] == '1' and next0[i] < n:
			dp[i] = max(dp[i], dp[next0[i] + 1] + 1)
		dp1[i] = dp1[i + 1]
		if next1[i] < n:
			dp1[i] = max(dp1[i], dp[next1[i] + 1] + 1)
	len1 = dp1[0] + 1
	curind = next1[0] + 1
	ans = '1'
	for i in range(1, len1):
		if curind >= n:
			ans = ans + '0'
			continue
		if next0[curind] >= n:
			ans = ans + '0'
			curind = next0[curind] + 1
			continue
		if dp[next0[curind] + 1] < len1 - i - 1:
			ans = ans + '0'
			curind = next0[curind] + 1
		else:
			ans = ans + '1'
			curind = next1[curind] + 1
	print(ans)
	return
t = int(input())
for i in range(t):
	solve()


from collections import defaultdict

def check(sub, oristr):
	m = len(sub)
	n = len(oristr)
	(i, j) = (0, 0)
	while j < m and i < n:
		if sub[j] == oristr[i]:
			j = j + 1
		i = i + 1
	return j == m

def method1(s):
	n = len(s)
	next0 = [0] * len(s)
	next1 = [0] * len(s)
	next0[n - 1] = n - 1 if s[n - 1] == '0' else n
	next1[n - 1] = n - 1 if s[n - 1] == '1' else n
	for i in range(len(s) - 2, -1, -1):
		next1[i] = i if s[i] == '1' else next1[i + 1]
		next0[i] = i if s[i] == '0' else next0[i + 1]
	s = s[::-1]
	dp = [0] * (n + 1)
	mxsize = 0
	cache = defaultdict(lambda : 0)
	group = 0
	flag = 0
	for (idx, i) in enumerate(s):
		cache[i] += 1
		if len(cache.keys()) == 2:
			mxsize += 1
			group += 1
			dp[idx] = group
			flag = 1
			cache = defaultdict(lambda : 0)
		dp[idx] = group
	dp = dp[::-1]
	dp = dp[1:]
	dp.extend([0])
	if flag:
		for i in '10':
			if i not in cache:
				mxsize += 2 if i == '0' else 1
				break
		curr = next1[0] + 1
		sortest = '1'
		for i in range(1, mxsize):
			if curr >= n:
				sortest += '0'
				continue
			if next0[curr] >= n:
				sortest += '0'
				curr = next0[curr] + 1
				continue
			if dp[next0[curr] + 1] < mxsize - i - 1:
				sortest += '0'
				curr = next0[curr] + 1
			else:
				sortest += '1'
				curr = next1[curr] + 1
		return sortest
	else:
		return '0' if s[-1] == '1' else '1'

def method2(s):
	i = 0
	flag = True
	while True:
		b = bin(i)[2:]
		i += 1
		if not check(b, s):
			return b
t = int(input())
for m in range(t):
	s = input()
	m1 = method1(s)
	print(m1)


import sys
t = int(input())
while t > 0:
	str = input()
	n = len(str)
	lp = -1
	n0 = [-1 for i in range(len(str))]
	n1 = [-1 for i in range(len(str))]
	dp1 = [-1 for i in range(len(str) + 2)]
	dp2 = [-1 for i in range(len(str) + 2)]
	for i in range(n):
		if str[i] == '0':
			for j in range(lp + 1, i + 1):
				n0[j] = i
			lp = i
	for i in range(lp + 1, n):
		n0[i] = n
	if n0[0] == n:
		print(0)
	else:
		lp = -1
		for i in range(n):
			if str[i] == '1':
				for j in range(lp + 1, i + 1):
					n1[j] = i
				lp = i
		for i in range(lp + 1, n):
			n1[i] = n
		dp1[n] = dp1[n + 1] = 0
		dp2[n] = dp2[n + 1] = 0
		for i in range(n - 1, -1, -1):
			dp1[i] = dp1[i + 1]
			if str[i] == '0' and n1[i] < n:
				dp1[i] = max(dp1[i], dp1[n1[i] + 1] + 1)
			if str[i] == '1' and n0[i] < n:
				dp1[i] = max(dp1[i], dp1[n0[i] + 1] + 1)
			dp2[i] = dp2[i + 1]
			if n1[i] < n:
				dp2[i] = max(dp2[i], dp1[n1[i] + 1] + 1)
		l = dp2[0] + 1
		index = n1[0] + 1
		result = '1'
		for i in range(1, l):
			if index >= n:
				result = result + '0'
				continue
			if n0[index] >= n:
				result = result + '0'
				index = n0[index] + 1
				continue
			if dp1[n0[index] + 1] < l - i - 1:
				result = result + '0'
				index = n0[index] + 1
			else:
				result = result + '1'
				index = n1[index] + 1
		print(result)
	t -= 1


q = int(input())
for i in range(q):
	w = list(map(str, input()))
	num0 = []
	num1 = []
	k = 0
	count = 0
	l = 0
	for j in range(len(w)):
		if w[j] == '0':
			num0.append(j)
			count = count + 1
			for m in range(k):
				num0.append(j)
			k = 0
		else:
			k = k + 1
	for m in range(k):
		num0.append(len(w))
	for j in range(len(w)):
		if w[j] == '1':
			num1.append(j)
			for m in range(l):
				num1.append(j)
			l = 0
		else:
			l = l + 1
	for m in range(l):
		num1.append(len(w))
	dp = [None] * (len(w) + 2)
	dp1 = [None] * (len(w) + 2)
	dp[len(w)] = dp1[len(w)] = dp[len(w) + 1] = dp1[len(w) + 1] = 0
	for j in range(len(w) - 1, -1, -1):
		dp[j] = dp[j + 1]
		if w[j] == '0' and num1[j] < len(w):
			dp[j] = max(dp[j], dp[num1[j] + 1] + 1)
		if w[j] == '1' and num0[j] < len(w):
			dp[j] = max(dp[j], dp[num0[j] + 1] + 1)
		dp1[j] = dp1[j + 1]
		if num1[j] < len(w):
			dp1[j] = max(dp1[j], dp[num1[j] + 1] + 1)
	lo = dp1[0] + 1
	x = num1[0] + 1
	ans = '1'
	for j in range(1, lo):
		if x >= len(w):
			ans = ans + '0'
			continue
		if num0[x] >= len(w):
			ans = ans + '0'
			continue
		if dp[num0[x] + 1] < lo - j - 1:
			ans = ans + '0'
			x = num0[x] + 1
		else:
			ans = ans + '1'
			x = num1[x] + 1
	if count == 0:
		print('0')
	else:
		print(ans)


def spar(s, n):
	if '0' not in s:
		print('0')
		return
	last_pos = -1
	(dp, dp1) = ([0] * (n + 2), [0] * (n + 2))
	(next0, next1) = ([0] * (n + 2), [0] * (n + 2))
	for i in range(n):
		if s[i] == '0':
			for j in range(last_pos + 1, i + 1):
				next0[j] = i
			last_pos = i
	for i in range(last_pos + 1, n):
		next0[i] = n
	last_pos = -1
	for i in range(n):
		if s[i] == '1':
			for j in range(last_pos + 1, i + 1):
				next1[j] = i
			last_pos = i
	for i in range(last_pos + 1, n):
		next1[i] = n
	dp[n] = dp[n + 1] = 0
	dp1[n] = dp1[n + 1] = 0
	for i in range(n - 1, -1, -1):
		dp[i] = dp[i + 1]
		if s[i] == '0' and next1[i] < n:
			dp[i] = max(dp[i], dp[next1[i] + 1] + 1)
		if s[i] == '1' and next0[i] < n:
			dp[i] = max(dp[i], dp[next0[i] + 1] + 1)
		dp1[i] = dp1[i + 1]
		if next1[i] < n:
			dp1[i] = max(dp1[i], dp[next1[i] + 1] + 1)
	length = dp1[0] + 1
	curind = next1[0] + 1
	ans = ['1']
	for i in range(1, length):
		if curind >= n:
			ans.append('0')
			continue
		if next0[curind] >= n:
			ans.append('0')
			curind = next0[curind] + 1
			continue
		if dp[next0[curind] + 1] < length - i - 1:
			ans.append('0')
			curind = next0[curind] + 1
		else:
			ans.append('1')
			curind = next1[curind] + 1
	print(''.join(map(str, ans)))
try:
	for _ in range(int(input())):
		s = input()
		n = len(s)
		spar(s, n)
except:
	pass


for _ in range(int(input())):
	s = input()
	if '0' not in s:
		print(0)
		continue
	if '1' not in s:
		print(1)
		continue
	start = s.index('1')
	s = s[start:]
	if '0' not in s:
		print(10)
		continue
	n = len(s)
	num0 = [n] * n
	num1 = [n] * n
	dp = [0] * (n + 5)
	dp1 = [0] * (n + 5)
	for i in range(n):
		if s[i] == '0':
			num0[i] = i
			k = i - 1
			while k >= 0 and num0[k] > i:
				num0[k] = i
				k -= 1
		if s[i] == '1':
			num1[i] = i
			k = i - 1
			while k >= 0 and num1[k] > i:
				num1[k] = i
				k -= 1
	for i in range(n - 1, -1, -1):
		dp[i] = dp[i + 1]
		if s[i] == '0' and num1[i] < n:
			dp[i] = max(dp[i], dp[num1[i] + 1] + 1)
		if s[i] == '1' and num0[i] < n:
			dp[i] = max(dp[i], dp[num0[i] + 1] + 1)
		dp1[i] = dp1[i + 1]
		if num1[i] < n:
			dp1[i] = max(dp1[i], dp[num1[i] + 1] + 1)
	ans = '1'
	l = dp1[0] + 1
	x = num1[0] + 1
	for i in range(1, l):
		if x >= n:
			ans += '0'
			continue
		if num0[x] >= n:
			ans += '0'
			x = num0[x] + 1
			continue
		if dp[num0[x] + 1] < l - i - 1:
			ans += '0'
			x = num0[x] + 1
			continue
		ans += '1'
		x = num1[x] + 1
	print(ans)


for t in range(int(input())):
	inputString = input()
	if inputString == '0' * len(inputString):
		print('1')
	else:
		some = 0
		while inputString[some] == '0':
			some += 1
		s = inputString[some:]
		n = len(s)
		next01 = [[-1, -1] for i in range(n)]
		queueForZero = []
		queueForOne = []
		for i in range(n):
			if s[i] == '0':
				for j in range(len(queueForZero)):
					next01[queueForZero[j]][0] = i
				queueForZero.clear()
			elif s[i] == '1':
				for j in range(len(queueForOne)):
					next01[queueForOne[j]][1] = i
				queueForOne.clear()
			queueForOne.append(i)
			queueForZero.append(i)
		if inputString == '1' * n:
			print('0')
		else:
			ans = '1'
			i = 0
			if next01[i][0] == -1:
				print('10')
			elif next01[i][1] == -1:
				print('11')
			else:
				x0 = next01[i][0]
				x1 = next01[i][1]
				while True:
					x0 = next01[i][0]
					x1 = next01[i][1]
					if x0 == -1:
						ans += '0'
						break
					if x1 == -1:
						ans += '1'
						break
					if x0 < x1:
						if next01[x0][0] == -1:
							ans += '00'
							break
						if next01[x1][0] == -1:
							ans += '10'
							break
						if next01[x1][1] == -1:
							ans += '11'
							break
					else:
						if next01[x0][0] == -1:
							ans += '00'
							break
						if next01[x0][1] == -1:
							ans += '01'
							break
						if next01[x1][1] == -1:
							ans += '11'
							break
					if x0 > 0 and x1 > 0 and (next01[x0][0] > 0) and (next01[x0][1] > 0) and (next01[x1][0] > 0) and (next01[1][1] > 0):
						if x0 > x1:
							ans += '0'
							i = x0
						elif x1 - x0 > 1:
							ans += '1'
							i = x1
						else:
							j = i + 1
							while j + 1 < n and s[j] == '0' and (s[j + 1] == '1'):
								j += 2
							if j == n:
								rem = (n - (i + 1)) // 2
								ans += '0' * rem
								ans += '0'
								break
							if s[j] == '1':
								rem = 1 + (j - (i + 1)) // 2
								ans += '0' * rem
								i = next01[j][0]
								if i == -1:
									break
							else:
								rem = (j - (i + 1)) // 2
								ans += '1' * rem
								i = j - 1
						continue
				print(ans)


def solve(s):
	if '0' not in s:
		return '0'
	if '1' not in s:
		return '1'
	n = len(s)
	nx0 = [n for i in range(n + 1)]
	nx1 = [n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		if s[i] == '0':
			nx0[i] = i
		else:
			nx0[i] = nx0[i + 1]
		if s[i] == '1':
			nx1[i] = i
		else:
			nx1[i] = nx1[i + 1]
	dp0 = [0 for i in range(n + 2)]
	dp1 = [0 for i in range(n + 2)]
	dp0[-1] = 0
	dp0[-2] = 0
	dp1[-1] = 0
	dp1[-2] = 0
	for i in range(n - 1, -1, -1):
		dp0[i] = dp0[i + 1]
		dp1[i] = dp1[i + 1]
		if s[i] == '0' and nx1[i] < n:
			dp0[i] = max(dp0[i], dp0[nx1[i] + 1] + 1)
		if s[i] == '1' and nx0[i] < n:
			dp0[i] = max(dp0[i], dp0[nx0[i] + 1] + 1)
		if nx1[i] < n:
			dp1[i] = max(dp1[i], dp0[nx1[i] + 1] + 1)
	ans_len = dp1[0] + 1
	ans = '1'
	pos = nx1[0] + 1
	for i in range(1, ans_len):
		if pos >= n:
			ans += '0'
			continue
		if nx0[pos] >= n:
			ans += '0'
			pos = nx0[pos] + 1
			continue
		if dp0[nx0[pos] + 1] < ans_len - i - 1:
			ans += '0'
			pos = nx0[pos] + 1
		else:
			ans += '1'
			pos = nx1[pos] + 1
	return ans

def gen():
	t = int(input())
	for _ in range(t):
		s = input()
		print(solve(s))
gen()


size = 10 ** 6
pos0 = [0] * size
pos1 = [0] * size
ary1 = [0] * (size + 2)
ary2 = [0] * (size + 2)
for _ in range(int(input())):
	s = str(input())
	s_len = len(s)
	last_pos_0 = -1
	last_pos_1 = -1
	for i in range(s_len):
		if s[i] == '0':
			for j in range(last_pos_0 + 1, i + 1):
				pos0[j] = i
			last_pos_0 = i
		else:
			for k in range(last_pos_1 + 1, i + 1):
				pos1[k] = i
			last_pos_1 = i
	for i in range(last_pos_0 + 1, s_len):
		pos0[i] = s_len
	if pos0[0] == s_len:
		print('0')
		continue
	for i in range(last_pos_1 + 1, s_len):
		pos1[i] = s_len
	ary1[s_len] = 0
	ary1[s_len + 1] = 0
	ary2[s_len] = 0
	ary2[s_len + 1] = 0
	for i in range(s_len - 1, -1, -1):
		ary1[i] = ary1[i + 1]
		ary2[i] = ary2[i + 1]
		if s[i] == '0' and pos1[i] < s_len:
			ary1[i] = max(ary1[i], ary1[pos1[i] + 1] + 1)
		if s[i] == '1' and pos0[i] < s_len:
			ary1[i] = max(ary1[i], ary1[pos0[i] + 1] + 1)
		if pos1[i] < s_len:
			ary2[i] = max(ary2[i], ary1[pos1[i] + 1] + 1)
	lenght = ary2[0] + 1
	index = pos1[0] + 1
	ans = '1'
	for i in range(1, lenght):
		if index >= s_len:
			ans += '0'
		elif pos0[index] >= s_len or ary1[pos0[index] + 1] < lenght - i - 1:
			ans += '0'
			index = pos0[index] + 1
		else:
			ans += '1'
			index = pos1[index] + 1
	print(ans)


nextzero = [0] * 1000000
nextone = [0] * 1000000
dp = [0] * 1000005
dp1 = [0] * 1000005

def solve():
	s = input()
	n = len(s)
	last = -1
	for i in range(n):
		if s[i] == '0':
			for j in range(last + 1, i + 1):
				nextzero[j] = i
				last = i
	for i in range(last + 1, n):
		nextzero[i] = n
	if nextzero[0] == n:
		return '0'
	last = -1
	for i in range(n):
		if s[i] == '1':
			for j in range(last + 1, i + 1):
				nextone[j] = i
				last = i
	for i in range(last + 1, n):
		nextone[i] = n
	dp[n] = 0
	dp[n + 1] = 0
	dp1[n] = 0
	dp1[n + 1] = 0
	for i in reversed(range(0, n)):
		dp[i] = dp[i + 1]
		if s[i] == '0' and nextone[i] < n:
			dp[i] = max(dp[i], dp[nextone[i] + 1] + 1)
		if s[i] == '1' and nextzero[i] < n:
			dp[i] = max(dp[i], dp[nextzero[i] + 1] + 1)
		dp1[i] = dp1[i + 1]
		if nextone[i] < n:
			dp1[i] = max(dp1[i], dp[nextone[i] + 1] + 1)
	l = dp1[0] + 1
	cur = nextone[0] + 1
	ans = '1'
	for i in range(1, l):
		if cur >= n:
			ans += '0'
			continue
		if nextzero[cur] >= n:
			ans += '0'
			cur = nextzero[cur] + 1
			continue
		if dp[nextzero[cur] + 1] < l - i - 1:
			ans += '0'
			cur = nextzero[cur] + 1
		else:
			ans += '1'
			cur = nextone[cur] + 1
	return ans
t = int(input())
for z in range(t):
	ans = solve()
	print(ans)


from sys import stdin, stdout
(readline, writeline) = (stdin.readline, stdout.write)
mx = 10 ** 6
dp0 = [0 for i in range(mx + 2)]
dp1 = [0 for i in range(mx + 2)]
next0 = [0 for i in range(mx)]
next1 = [0 for i in range(mx)]

def solve(s):
	last_pos = -1
	l = len(s)
	for i in range(l):
		if s[i] == '0':
			for j in range(last_pos + 1, i + 1):
				next0[j] = i
			last_pos = i
	for i in range(last_pos + 1, l):
		next0[i] = l
	if next0[0] == l:
		print('0')
		return
	last_pos = -1
	for i in range(l):
		if s[i] == '1':
			for j in range(last_pos + 1, i + 1):
				next1[j] = i
			last_pos = i
	for i in range(last_pos + 1, l):
		next1[i] = l
	dp0[l] = dp0[l + 1] = 0
	dp1[l] = dp1[l + 1] = 0
	for i in range(l - 1, -1, -1):
		dp0[i] = dp0[i + 1]
		if s[i] == '0' and next1[i] < l:
			dp0[i] = max(dp0[i], dp0[next1[i] + 1] + 1)
		if s[i] == '1' and next0[i] < l:
			dp0[i] = max(dp0[i], dp0[next0[i] + 1] + 1)
		dp1[i] = dp1[i + 1]
		if next1[i] < l:
			dp1[i] = max(dp1[i], dp0[next1[i] + 1] + 1)
	length = dp1[0] + 1
	curind = next1[0] + 1
	ans = '1'
	for i in range(1, length):
		if curind >= l:
			ans += '0'
			continue
		if next0[curind] >= l:
			ans += '0'
			curind = next0[curind] + 1
			continue
		if dp0[next0[curind] + 1] < length - i - 1:
			ans += '0'
			curind = next0[curind] + 1
		else:
			ans += '1'
			curind = next1[curind] + 1
	print(ans)
for _ in range(int(readline())):
	s = input()
	solve(s)


for _ in range(int(input())):
	s = input()
	n = len(s)
	m = n
	z_pos = n
	o_pos = n
	i = n - 1
	z = [0] * n
	o = [0] * n
	while i >= 0:
		if s[i] == '1':
			o_pos = i
		else:
			z_pos = i
		z[i] = z_pos
		o[i] = o_pos
		i = i - 1
	if z[0] == n:
		print('0')
		continue
	if o[0] == n:
		print('1')
		continue
	res = '1'
	dp = [0] * (n + 2)
	k = [0] * (n + 2)
	i = n - 1
	while i >= 0:
		dp[i] = dp[i + 1]
		k[i] = k[i + 1]
		if s[i] == '0':
			if o[i] < n:
				dp[i] = max(dp[i], dp[o[i] + 1] + 1)
		elif z[i] < n:
			dp[i] = max(dp[i], dp[z[i] + 1] + 1)
		if o[i] < n:
			k[i] = max(k[i], dp[o[i] + 1] + 1)
		if i == 0:
			m = k[i] + 1
			pos = o[i] + 1
		i = i - 1
	for i in range(1, m):
		if pos >= n:
			res = res + '0'
			continue
		if z[pos] >= n:
			pos = z[pos] + 1
			res = res + '0'
			continue
		if dp[z[pos] + 1] >= m - i - 1:
			pos = o[pos] + 1
			res = res + '1'
		else:
			pos = z[pos] + 1
			res = res + '0'
	print(res)


inf = 10 ** 6
a1 = [0] * inf
a2 = [0] * inf
a3 = [0] * (inf + 2)
a4 = [0] * (inf + 2)
t = int(input())
for i in range(t):
	s = input()
	l = len(s)
	q = -1
	for w in range(0, l):
		if s[w] == '0':
			for k in range(q + 1, w + 1):
				a1[k] = w
				q = w
	for y in range(q + 1, l):
		a1[y] = l
	if a1[0] == l:
		print(0)
		continue
	q = -1
	for w in range(0, l):
		if s[w] == '1':
			for k in range(q + 1, w + 1):
				a2[k] = w
				q = w
	for r in range(q + 1, l):
		a2[r] = l
	a3[l] = a3[l + 1] = 0
	a4[l] = a4[l + 1] = 0
	for e in range(l - 1, -1, -1):
		a3[e] = a3[e + 1]
		if s[e] == '0' and a2[e] < l:
			a3[e] = max(a3[e], a3[a2[e] + 1] + 1)
		if s[e] == '1' and a1[e] < l:
			a3[e] = max(a3[e], a3[a1[e] + 1] + 1)
		a4[e] = a4[e + 1]
		if a2[e] < l:
			a4[e] = max(a4[e], a3[a2[e] + 1] + 1)
	x = a4[0] + 1
	c = a2[0] + 1
	a = '1'
	for g in range(1, x):
		if c >= l:
			a += '0'
			continue
		if a1[c] >= l:
			a += '0'
			c = a1[c] + 1
			continue
		if a3[a1[c] + 1] < x - g - 1:
			a += '0'
			c = a1[c] + 1
		else:
			a += '1'
			c = a2[c] + 1
	print(a)


maxn = 10 ** 6
(dp, dp1, next0, next1) = ([''] * (maxn + 2), [''] * (maxn + 2), [''] * maxn, [''] * maxn)

def solve():
	s = input()
	n = len(s)
	last = -1
	for i in range(n):
		if s[i] == '0':
			for j in range(last + 1, i + 1):
				next0[j] = i
			last = i
	for i in range(last + 1, n):
		next0[i] = n
	if next0[0] == n:
		print(0)
		return
	last = -1
	for i in range(n):
		if s[i] == '1':
			for j in range(last + 1, i + 1):
				next1[j] = i
			last = i
	for i in range(last + 1, n):
		next1[i] = n
	(dp[n], dp[n + 1], dp1[n], dp1[n + 1]) = (0, 0, 0, 0)
	for i in range(n - 1, -1, -1):
		dp[i] = dp[i + 1]
		if s[i] == '0' and next1[i] < n:
			dp[i] = max(dp[i], dp[next1[i] + 1] + 1)
		if s[i] == '1' and next0[i] < n:
			dp[i] = max(dp[i], dp[next0[i] + 1] + 1)
		dp1[i] = dp[i + 1]
		if next1[i] < n:
			dp1[i] = max(dp1[i], dp[next1[i] + 1] + 1)
	l = dp1[0] + 1
	ind = next1[0] + 1
	ans = '1'
	for i in range(1, l):
		if ind >= n:
			ans += '0'
			continue
		if next0[ind] >= n:
			ans += '0'
			ind = next0[ind] + 1
			continue
		if dp[next0[ind] + 1] < l - i - 1:
			ans += '0'
			ind = next0[ind] + 1
		else:
			ans += '1'
			ind = next1[ind] + 1
	print(ans)
for _ in range(int(input())):
	solve()


import collections
import sys
sys.setrecursionlimit(10 ** 6)

def makegroups(st):
	pr = -1
	count = 0
	N = 0
	res = []
	for ch in st:
		im = 1 if ch == '1' else 0
		if im == pr:
			count += 1
		else:
			if count != 0:
				count = min(count, 3)
				N += count
				res.append(count)
			pr = im
			count = 1
	if count != 0:
		count = min(count, 3)
		N += count
		res.append(count)
	return (N, res)

def dfs(el):
	distance = [-1] * (len(el) >> 1)
	distance[0] = 0
	fifo = collections.deque([(0, 1, 1, 1)])
	while fifo:
		(parent, child, bit, dist) = fifo.popleft()
		if distance[child] == -1:
			distance[child] = dist
			el[(parent << 1) + bit] = child
			for b2 in range(2):
				c2 = el[(child << 1) + b2]
				if c2 != -1:
					fifo.append((child, c2, b2, dist + 1))
			el[child << 1] = -1
			el[(child << 1) + 1] = -1
		elif distance[child] == dist:
			el[(parent << 1) + bit] = child

def isOnPath(vertex, result, known, el):
	if known[vertex]:
		return result[vertex]
	vi0 = vertex << 1
	vi1 = vi0 + 1
	if el[vi0] == -1 and el[vi1] == -1:
		result[vertex] = False
	elif el[vi0] == -1:
		result[vertex] = isOnPath(el[vi1], result, known, el)
	elif el[vi1] == -1:
		result[vertex] = isOnPath(el[vi0], result, known, el)
	else:
		result[vertex] = isOnPath(el[vi0], result, known, el) or isOnPath(el[vi1], result, known, el)
	known[vertex] = True
	return result[vertex]

def printPath(endv, vonpath, el):
	vertex = 0
	result = []
	while vertex != endv:
		vi0 = vertex << 1
		vi1 = vi0 + 1
		if el[vi0] != -1 and el[vi1] != -1:
			if vonpath[el[vi0]]:
				result.append(0)
				vertex = el[vi0]
			else:
				result.append(1)
				vertex = el[vi1]
		elif el[vi0] == -1:
			result.append(1)
			vertex = el[vi1]
		else:
			result.append(0)
			vertex = el[vi0]
	print(*result, sep='')

def solve(st):
	(N, groups) = makegroups(st)
	firstone = st[0] == '1'
	if len(groups) == 1:
		if firstone:
			print(0)
			return
		else:
			print(1)
			return
	if not firstone:
		N -= groups[0]
	el = [-1] * (2 * (N + 2))
	vertex = 1
	bit = 1
	for index in range(0 if firstone else 1, len(groups)):
		count = groups[index]
		jump = vertex + count + (0 if index == len(groups) - 1 else groups[index + 1])
		for v in range(vertex, vertex + count - 1):
			el[(v << 1) + bit] = v + 1
			el[(v << 1) + (1 - bit)] = vertex + count
		v = vertex + count - 1
		el[(v << 1) + bit] = jump
		el[(v << 1) + (1 - bit)] = vertex + count
		vertex += count
		bit = 1 - bit
	dfs(el)
	vonpath = [False] * (N + 1) + [True]
	isOnPath(0, vonpath, vonpath[:], el)
	printPath(N + 1, vonpath, el)
for _ in range(int(input())):
	solve(input())


def solve():
	string = input()
	le = len(string)
	first_list = []
	second_list = []
	dp0 = [0, 0]
	dp1 = [0, 0]
	prev0 = 0
	prev1 = 0
	for i in range(le):
		if string[i] == '0':
			for j in range(prev0, i + 1):
				first_list.append(i)
				dp0.append(0)
				prev0 = i + 1
		elif string[i] == '1':
			for k in range(prev1, i + 1):
				second_list.append(i)
				dp1.append(0)
				prev1 = i + 1
	if len(first_list) == 0:
		print(0)
		return
	if len(second_list) == 0:
		print(1)
		return
	if len(first_list) > len(second_list):
		for i in range(len(second_list), len(first_list)):
			second_list.append(le)
			dp1.append(0)
	elif len(first_list) < len(second_list):
		for i in range(len(first_list), len(second_list)):
			first_list.append(le)
			dp0.append(0)
	for i in reversed(range(le)):
		dp0[i] = dp0[i + 1]
		if string[i] == '0' and second_list[i] < le:
			dp0[i] = max(dp0[i], dp0[second_list[i] + 1] + 1)
		if string[i] == '1' and first_list[i] < le:
			dp0[i] = max(dp0[i], dp0[first_list[i] + 1] + 1)
		dp1[i] = dp1[i + 1]
		if second_list[i] < le:
			dp1[i] = max(dp1[i], dp0[second_list[i] + 1] + 1)
	l = dp1[0] + 1
	x = second_list[0] + 1
	final_ans = '1'
	for i in range(1, l):
		if x >= le:
			final_ans += '0'
			continue
		if first_list[x] >= le:
			final_ans += '0'
			x = first_list[x] + 1
			continue
		if dp0[first_list[x] + 1] < l - i - 1:
			final_ans += '0'
			x = first_list[x] + 1
		else:
			final_ans += '1'
			x = second_list[x] + 1
	print(final_ans)
for _ in range(int(input())):
	solve()


T = int(input())
for _ in range(T):
	S = input()
	L = len(S)
	N0 = []
	N1 = []
	dp0 = [0, 0]
	dp1 = [0, 0]
	prev0 = 0
	prev1 = 0
	for i in range(L):
		if S[i] == '0':
			for j in range(prev0, i + 1):
				N0.append(i)
				dp0.append(0)
				prev0 = i + 1
		elif S[i] == '1':
			for k in range(prev1, i + 1):
				N1.append(i)
				dp1.append(0)
				prev1 = i + 1
	if len(N0) == 0:
		print(0)
		continue
	if len(N1) == 0:
		print(1)
		continue
	if len(N0) > len(N1):
		for i in range(len(N1), len(N0)):
			N1.append(L)
			dp1.append(0)
	elif len(N0) < len(N1):
		for i in range(len(N0), len(N1)):
			N0.append(L)
			dp0.append(0)
	for i in reversed(range(L)):
		dp0[i] = dp0[i + 1]
		if S[i] == '0' and N1[i] < L:
			dp0[i] = max(dp0[i], dp0[N1[i] + 1] + 1)
		if S[i] == '1' and N0[i] < L:
			dp0[i] = max(dp0[i], dp0[N0[i] + 1] + 1)
		dp1[i] = dp1[i + 1]
		if N1[i] < L:
			dp1[i] = max(dp1[i], dp0[N1[i] + 1] + 1)
	l = dp1[0] + 1
	x = N1[0] + 1
	Ans = '1'
	for i in range(1, l):
		if x >= L:
			Ans += '0'
			continue
		if N0[x] >= L:
			Ans += '0'
			x = N0[x] + 1
			continue
		if dp0[N0[x] + 1] < l - i - 1:
			Ans += '0'
			x = N0[x] + 1
		else:
			Ans += '1'
			x = N1[x] + 1
	print(Ans)


size = 1000000
arr1 = [None] * (size + 2)
arr2 = [None] * (size + 2)
mat1 = [None] * size
mat2 = [None] * size

def binarystring(string):
	n = len(string)
	pos = -1
	for i in range(n):
		if string[i] == '0':
			for j in range(pos + 1, i + 1):
				mat1[j] = i
				pos = i
	for i in range(pos + 1, n):
		mat1[i] = n
	if mat1[0] == n:
		print('0\n')
		return
	pos = -1
	for i in range(n):
		if string[i] == '1':
			for j in range(pos + 1, i + 1):
				mat2[j] = i
				pos = i
	for i in range(pos + 1, n):
		mat2[i] = n
	arr1[n] = arr1[n + 1] = 0
	arr2[n] = arr2[n + 1] = 0
	i = n - 1
	while i >= 0:
		arr1[i] = arr1[i + 1]
		if string[i] == '0' and mat2[i] < n:
			arr1[i] = max(arr1[i], arr1[mat2[i] + 1] + 1)
		if string[i] == '1' and mat1[i] < n:
			arr1[i] = max(arr1[i], arr1[mat1[i] + 1] + 1)
		arr2[i] = arr2[i + 1]
		if mat2[i] < n:
			arr2[i] = max(arr2[i], arr1[mat2[i] + 1] + 1)
		i -= 1
	len_ = arr2[0] + 1
	currentind = mat2[0] + 1
	ans = '1'
	for i in range(1, len_):
		if currentind >= n:
			ans += '0'
			continue
		if mat1[currentind] >= n:
			ans += '0'
			currentind = mat1[currentind] + 1
			continue
		if arr1[mat1[currentind] + 1] < len_ - i - 1:
			ans += '0'
			currentind = mat1[currentind] + 1
		else:
			ans += '1'
			currentind = mat2[currentind] + 1
	print(ans)
t = int(input())
while t > 0:
	string = input()
	binarystring(string)
	t -= 1


from sys import stdin, stdout, setrecursionlimit
from math import ceil
t = int(stdin.readline())
for _ in range(t):
	a = input()
	N = len(a)
	n0 = [N] * N
	n1 = [N] * N
	t0 = [0] * (N + 2)
	t1 = [0] * (N + 2)
	lp = -1
	for i in range(N):
		if a[i] == '0':
			for j in range(lp + 1, i + 1):
				n0[j] = i
				lp = i
	for i in range(lp + 1, N):
		n0[i] = N
	if n0[0] == N:
		print(0)
		continue
	lp = -1
	for i in range(N):
		if a[i] == '1':
			for j in range(lp + 1, i + 1):
				n1[j] = i
				lp = i
	for i in range(lp + 1, N):
		n1[i] = N
	for i in range(N - 1, -1, -1):
		t0[i] = t0[i + 1]
		if a[i] == '0' and n1[i] < N:
			t0[i] = max(t0[i], t0[n1[i] + 1] + 1)
		if a[i] == '1' and n0[i] < N:
			t0[i] = max(t0[i], t0[n0[i] + 1] + 1)
		t1[i] = t1[i + 1]
		if n1[i] < N:
			t1[i] = max(t1[i], t0[n1[i] + 1] + 1)
	l = t1[0] + 1
	x = n1[0] + 1
	ans = '1'
	for i in range(1, l):
		if x >= N:
			ans += '0'
			continue
		if n0[x] >= N:
			ans += '0'
			x = n0[x] + 1
			continue
		if t0[n0[x] + 1] < l - i - 1:
			ans += '0'
			x = n0[x] + 1
		else:
			ans += '1'
			x = n1[x] + 1
	print(ans)


for _ in range(int(input())):
	s = input()
	n = len(s)
	zeros = [n] * n
	ones = [n] * n
	DPini = [None] * n + [0, 0]
	DPfin = [None] * n + [0, 0]
	prev = -1
	for x in range(len(s)):
		if s[x] == '0':
			for y in range(prev + 1, x + 1):
				zeros[y] = x
			prev = x
	prev = -1
	for x in range(len(s)):
		if s[x] == '1':
			for y in range(prev + 1, x + 1):
				ones[y] = x
			prev = x
	if zeros[0] == n:
		print('0')
		continue
	if ones[0] == n:
		print('1')
		continue
	for x in range(n - 1, -1, -1):
		DPini[x] = DPini[x + 1]
		if s[x] == '0' and ones[x] < n:
			DPini[x] = max(DPini[x], DPini[ones[x] + 1] + 1)
		if s[x] == '1' and zeros[x] < n:
			DPini[x] = max(DPini[x], DPini[zeros[x] + 1] + 1)
		DPfin[x] = DPfin[x + 1]
		if ones[x] < n:
			DPfin[x] = max(DPfin[x], DPini[ones[x] + 1] + 1)
	l = DPfin[0] + 1
	a = ones[0] + 1
	sol = '1'
	for x in range(1, l):
		if a >= n:
			sol += '0'
		elif zeros[a] >= n:
			sol += '0'
			a = zeros[a] + 1
		elif DPini[zeros[a] + 1] < l - x - 1:
			sol += '0'
			a = zeros[a] + 1
		else:
			sol += '1'
			a = ones[a] + 1
	print(sol)


m = 1000000
(a, b) = ([0] * m, [0] * m)
(d0, d1) = ([0] * (m + 2), [0] * (m + 2))

def mac():
	s = input()
	n = len(s)
	pos = -1
	for i in range(n):
		if s[i] == '0':
			for j in range(pos + 1, i + 1):
				a[j] = i
			pos = i
	for i in range(pos + 1, n):
		a[i] = n
	if a[0] == n:
		return '0'
	pos = -1
	for i in range(n):
		if s[i] == '1':
			for j in range(pos + 1, i + 1):
				b[j] = i
			pos = i
		if s[i] == '1' and a[i] < n:
			d0[i] = max(d0[i], d0[a[i] + 1] + 1)
		d1[i] = d1[i + 1]
		if b[i] < n:
			d1[i] = max(d1[i], d0[b[i] + 1] + 1)
	for i in range(pos + 1, n):
		b[i] = n
	d0[n + 1] = d0[n] = 0
	d1[n + 1] = d1[n] = 0
	for i in range(n - 1, -1, -1):
		d0[i] = d0[i + 1]
		if s[i] == '0' and b[i] < n:
			d0[i] = max(d0[i], d0[b[i] + 1] + 1)
		if s[i] == '1' and a[i] < n:
			d0[i] = max(d0[i], d0[a[i] + 1] + 1)
		d1[i] = d1[i + 1]
		if b[i] < n:
			d1[i] = max(d1[i], d0[b[i] + 1] + 1)
	x = d1[0] + 1
	count = b[0] + 1
	ans = '1'
	for i in range(1, x):
		if count >= n:
			ans += '0'
			continue
		if a[count] >= n:
			ans += '0'
			count = a[count] + 1
			continue
		if d0[a[count] + 1] < x - i - 1:
			ans += '0'
			count = a[count] + 1
		else:
			ans += '1'
			count = b[count] + 1
	return ans
for _ in range(int(input())):
	print(mac())


INT_MAX = int(1000000.0)
(next0, next1) = ([-1] * INT_MAX, [-1] * INT_MAX)
(dp, dp1) = ([-1] * (INT_MAX + 2), [-1] * (INT_MAX + 2))

def stringMex(s):
	n = len(s)
	pos = -1
	for i in range(n):
		if s[i] == '0':
			for j in range(pos + 1, i + 1):
				next0[j] = i
			pos = i
	for i in range(pos + 1, n):
		next0[i] = n
	if next0[0] == n:
		print('0')
		return
	pos = -1
	for i in range(n):
		if s[i] == '1':
			for j in range(pos + 1, i + 1):
				next1[j] = i
			pos = i
	for i in range(pos + 1, n):
		next1[i] = n
	(dp[n], dp[n + 1]) = (0, 0)
	(dp1[n], dp1[n + 1]) = (0, 0)
	for i in range(n - 1, -1, -1):
		dp[i] = dp[i + 1]
		if s[i] == '0' and next1[i] < n:
			dp[i] = max(dp[i], dp[next1[i] + 1] + 1)
		if s[i] == '1' and next0[i] < n:
			dp[i] = max(dp[i], dp[next0[i] + 1] + 1)
		dp1[i] = dp1[i + 1]
		if next1[i] < n:
			dp1[i] = max(dp1[i], dp[next1[i] + 1] + 1)
	x = dp1[0] + 1
	count = next1[0] + 1
	ans = '1'
	for i in range(1, x):
		if count >= n:
			ans += '0'
			continue
		if next0[count] >= n:
			ans += '0'
			count = next0[count] + 1
			continue
		if dp[next0[count] + 1] < x - i - 1:
			ans += '0'
			count = next0[count] + 1
		else:
			ans += '1'
			count = next1[count] + 1
	print(ans)
	return
for _ in range(int(input())):
	stringMex(input())


T = int(input())
for t in range(T):
	binary_string = str(input())
	n = len(binary_string)
	num_zero = [-1] * n
	num_one = [-1] * n
	last_zero = n
	last_one = n
	for i in range(n - 1, -1, -1):
		if binary_string[i] == '1':
			last_one = i
		else:
			last_zero = i
		num_zero[i] = last_zero
		num_one[i] = last_one
	dp = [-1] * (n + 2)
	dp_1 = [-1] * (n + 2)
	dp[n] = 0
	dp[n + 1] = 0
	dp_1[n] = 0
	dp_1[n + 1] = 0
	for i in range(n - 1, -1, -1):
		dp[i] = dp[i + 1]
		if binary_string[i] == '0' and num_one[i] < n:
			dp[i] = max(dp[i], dp[num_one[i] + 1] + 1)
		if binary_string[i] == '1' and num_zero[i] < n:
			dp[i] = max(dp[i], dp[num_zero[i] + 1] + 1)
		dp_1[i] = dp_1[i + 1]
		if num_one[i] < n:
			dp_1[i] = max(dp_1[i], dp[num_one[i] + 1] + 1)
	ans_size = dp_1[0] + 1
	x = num_one[0] + 1
	if '0' in binary_string:
		ans = '1'
		for i in range(1, ans_size):
			if x >= n:
				ans += '0'
			elif num_zero[x] >= n:
				x = num_zero[x] + 1
				ans += '0'
			elif dp[num_zero[x] + 1] < ans_size - i - 1:
				x = num_zero[x] + 1
				ans += '0'
			else:
				x = num_one[x] + 1
				ans += '1'
	else:
		ans = '0'
	print(ans)


for i in range(int(input())):
	s = input()
	n = len(s)
	i = 0
	zero = [0] * n
	one = [0] * n
	dp0 = [0] * (n + 2)
	dp1 = [0] * (n + 2)
	pos = -1
	for i in range(n):
		if s[i] == '0':
			for j in range(pos + 1, i + 1):
				zero[j] = i
			pos = i
	for i in range(pos + 1, n):
		zero[i] = n
	if zero[0] == n:
		print(0)
	else:
		pos = -1
		for i in range(n):
			if s[i] == '1':
				for j in range(pos + 1, i + 1):
					one[j] = i
				pos = i
		for i in range(pos + 1, n):
			one[i] = n
		for i in range(n - 1, -1, -1):
			dp0[i] = dp0[i + 1]
			if s[i] == '0' and one[i] < n:
				dp0[i] = max(dp0[i], dp0[one[i] + 1] + 1)
			if s[i] == '1' and zero[i] < n:
				dp0[i] = max(dp0[i], dp0[zero[i] + 1] + 1)
			dp1[i] = dp1[i + 1]
			if one[i] < n:
				dp1[i] = max(dp1[i], dp0[one[i] + 1] + 1)
		x = dp1[0] + 1
		ans = '1'
		count = one[0] + 1
		for i in range(1, x):
			if count >= n:
				ans += '0'
				continue
			if zero[count] >= n:
				ans += '0'
				count = zero[count] + 1
				continue
			if dp0[zero[count] + 1] < x - i - 1:
				ans += '0'
				count = zero[count] + 1
			else:
				ans += '1'
				count = one[count] + 1
		print(ans)


t = int(input())
while t > 0:
	s = input()
	t -= 1
	n = len(s)
	if s.count('1') == n:
		print(0)
	elif s.count('0') == n:
		print(1)
	else:
		ind = 0
		while s[ind] == '0':
			ind += 1
		if s[-1] == '0':
			dp = [0] * (n + 1)
			zero = [0] * (n + 1)
			for i in range(n - 1, -1, -1):
				if s[i] == '0':
					zero[i] = zero[i + 1] + 1
				else:
					zero[i] = zero[i + 1]
			n0_m1 = 2
			ind_m1 = n
			n0_m2 = 2
			ind_m2 = n - 1
			n1 = 1
			ind_n1 = -1
			dp[n - 1] = -1
			for i in range(n - 2, -1, -1):
				if s[i] == '0':
					dp[i] = ind_n1
					if n1 < n0_m2:
						if n1 < n0_m1:
							n0_m2 = n0_m1 + 1
							ind_m2 = ind_m1
							n0_m1 = n1 + 1
							ind_m1 = i
						else:
							n0_m1 = n0_m1 + 1
							n0_m2 = n1 + 1
							ind_m2 = i
					else:
						n0_m1 += 1
						n0_m2 += 1
				else:
					if n1 < n0_m1:
						dp[i] = ind_n1
						n1 = n1 + 1
					else:
						dp[i] = ind_m1
						n1 = 1 + n0_m1
					ind_n1 = i
		else:
			dp = [0] * (n + 1)
			zero = [0] * (n + 1)
			for i in range(n - 1, -1, -1):
				if s[i] == '0':
					zero[i] = zero[i + 1] + 1
				else:
					zero[i] = zero[i + 1]
			n0_m1 = 1
			ind_m1 = n
			n0_m2 = 999999999
			ind_m2 = -1
			n1 = 2
			ind_n1 = n - 1
			dp[n - 1] = n
			for i in range(n - 2, -1, -1):
				if s[i] == '0':
					dp[i] = ind_n1
					if n1 < n0_m2:
						if n1 < n0_m1:
							n0_m2 = n0_m1 + 1
							ind_m2 = ind_m1
							n0_m1 = n1 + 1
							ind_m1 = i
						else:
							n0_m1 = n0_m1 + 1
							n0_m2 = n1 + 1
							ind_m2 = i
					else:
						n0_m1 += 1
						n0_m2 += 1
				else:
					if n1 < n0_m1:
						dp[i] = ind_n1
						n1 = n1 + 1
					else:
						dp[i] = ind_m1
						n1 = 1 + n0_m1
					ind_n1 = i
		prev = 0
		i = ind
		while i <= n:
			if i == -1:
				print('1', end='')
				break
			elif i == n:
				count_0 = zero[prev]
				for j in range(count_0):
					print('0', end='')
				print('0', end='')
				break
			elif s[i] == '0':
				count_0 = zero[prev] - zero[i]
				for j in range(count_0):
					print('0', end='')
				print('0', end='')
				prev = i
				i = dp[prev]
			else:
				print('1', end='')
				prev = i
				i = dp[prev]
		print()


from sys import *
from itertools import *
from math import *
from sys import *
from numpy import *
from sys import stdin, stdout
int_arr = lambda : list(map(int, stdin.readline().strip().split()))
str_arr = lambda : list(map(str, stdin.readline().split()))
get_str = lambda : map(str, stdin.readline().strip().split())
get_int = lambda : map(int, stdin.readline().strip().split())
get_float = lambda : map(float, stdin.readline().strip().split())
mod = 1000000007

def ans(s):
	(next0, next1) = ([0] * len(s), [0] * len(s))
	(dp, dp1) = ([0] * (len(s) + 1), [0] * (len(s) + 1))
	n = len(s)
	l_pos = -1
	for i in range(0, n):
		if s[i] == '0':
			for j in range(l_pos + 1, i + 1):
				next0[j] = i
				l_pos = i
	for i in range(l_pos + 1, n):
		next0[i] = n
	if next0[0] == n:
		print('0')
		return
	l_pos = -1
	for i in range(0, n):
		if s[i] == '1':
			for j in range(l_pos + 1, i + 1):
				next1[j] = i
				l_pos = i
	for i in range(l_pos + 1, n):
		next1[i] = n
	for i in range(n - 1, -1, -1):
		dp[i] = dp[i + 1]
		if s[i] == '0' and next1[i] < n:
			dp[i] = max(dp[i], dp[next1[i] + 1] + 1)
		if s[i] == '1' and next0[i] < n:
			dp[i] = max(dp[i], dp[next0[i] + 1] + 1)
			dp1[i] = dp1[i + 1]
		if next1[i] < n:
			dp1[i] = max(dp1[i], dp[next1[i] + 1] + 1)
	l = dp1[0] + 1
	curind = next1[0] + 1
	ans = '1'
	for i in range(1, l):
		if curind >= n:
			ans += '0'
			continue
		if next0[curind] >= n:
			ans += '0'
			curind = next0[curind] + 1
			continue
		if dp[next0[curind] + 1] < l - i - 1:
			ans += '0'
			curind = next0[curind] + 1
		else:
			ans += '1'
			curind = next1[curind] + 1
	print(ans)
	return
for _ in range(int(stdin.readline())):
	s = str(input())
	ans(s)


t = int(input())

def logic():
	s = input()
	n = len(s)
	MAXN = n
	dp = [0] * (MAXN + 2)
	dp1 = [0] * (MAXN + 2)
	next0 = [0] * MAXN
	next1 = [0] * MAXN
	last_pos = -1
	for i in range(n):
		if s[i] == '0':
			for j in range(last_pos + 1, i + 1):
				next0[j] = i
				last_pos = i
	for i in range(last_pos + 1, n):
		next0[i] = n
	if next0[0] == n:
		print('0')
		return
	last_pos = -1
	for i in range(n):
		if s[i] == '1':
			for j in range(last_pos + 1, i + 1):
				next1[j] = i
				last_pos = i
	for i in range(last_pos + 1, n):
		next1[i] = n
	dp[n] = dp[n + 1] = 0
	dp1[n] = dp1[n + 1] = 0
	for i in range(n - 1, -1, -1):
		dp[i] = dp[i + 1]
		if s[i] == '0' and next1[i] < n:
			dp[i] = max(dp[i], dp[next1[i] + 1] + 1)
		if s[i] == '1' and next0[i] < n:
			dp[i] = max(dp[i], dp[next0[i] + 1] + 1)
		dp1[i] = dp1[i + 1]
		if next1[i] < n:
			dp1[i] = max(dp1[i], dp[next1[i] + 1] + 1)
	ln = dp1[0] + 1
	curind = next1[0] + 1
	ans = '1'
	for i in range(1, ln):
		if curind >= n:
			ans += '0'
			continue
		if next0[curind] >= n:
			ans += '0'
			curind = next0[curind] + 1
			continue
		if dp[next0[curind] + 1] < ln - i - 1:
			ans += '0'
			curind = next0[curind] + 1
		else:
			ans += '1'
			curind = next1[curind] + 1
	print(ans)
for _ in range(t):
	logic()


import sys
import math
import collections
from sys import stdin, stdout, setrecursionlimit
import bisect as bs
setrecursionlimit(2 ** 20)
M = 10 ** 9 + 7
T = int(stdin.readline())

def checkSub(s, t):
	S = len(s)
	T = len(t)
	i = 0
	j = 0
	while i < S and j < T:
		if s[i] == t[j]:
			j += 1
			i += 1
		else:
			i += 1
		if j == T:
			return True
	return False
for _ in range(T):
	s = stdin.readline().strip('\n')
	z = s.count('0')
	o = len(s) - z
	if o == 0:
		print(1)
		continue
	if z == 0:
		print(0)
		continue
	n = len(s)
	ix = s.find('1')
	loc = {}
	loc['1'] = n
	loc['0'] = n
	dp = [0] * (n + 2)
	dp[n] = 1
	no = [0] * n
	nz = [0] * n
	for i in range(n - 1, -1, -1):
		loc[s[i]] = i
		dp[i] = min(1 + dp[loc['1'] + 1], 1 + dp[loc['0'] + 1])
		no[i] = loc['1']
		nz[i] = loc['0']
	i = ix + 1
	ans = '1'
	while i < n:
		if dp[no[i] + 1] < dp[nz[i] + 1]:
			ans += '1'
			i = no[i] + 1
		else:
			ans += '0'
			i = nz[i] + 1
	if i == n:
		ans += '0'
	print(ans)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	s = [int(d) for d in list(input())[:-1]]
	n = len(s)
	yyy = [-1] * (n + 2)
	xxx = [-1] * (n + 2)
	nanimono = -1
	for i in range(n):
		if not s[i]:
			for j in range(nanimono + 1, i + 1):
				yyy[j] = i
				nanimono = i
	for i in range(nanimono + 1, n):
		yyy[i] = n
	if yyy[0] == n:
		print(0)
		continue
	nanimono = -1
	for i in range(n):
		if s[i]:
			for j in range(nanimono + 1, i + 1):
				xxx[j] = i
			nanimono = i
	xyy = [-1] * (n + 2)
	xyx = [-1] * (n + 2)
	xyx[n] = xyx[n + 1] = 0
	xyy[n] = xyy[n + 1] = 0
	for i in range(nanimono + 1, n):
		xxx[i] = n
	for i in range(n - 1, -1, -1):
		xyy[i] = xyy[i + 1]
		if not s[i] and xxx[i] < n:
			xyy[i] = max(xyy[i], xyy[xxx[i] + 1] + 1)
		if s[i] and yyy[i] < n:
			xyy[i] = max(xyy[i], xyy[yyy[i] + 1] + 1)
		xyx[i] = xyx[i + 1]
		if xxx[i] < n:
			xyx[i] = max(xyx[i], xyy[xxx[i] + 1] + 1)
	ind = xxx[0] + 1
	ans = '1'
	warida = xyx[0] + 1
	for i in range(1, warida):
		if ind >= n:
			ans += '0'
			continue
		elif yyy[ind] >= n:
			ans += '0'
			ind = yyy[ind] + 1
			continue
		if xyy[yyy[ind] + 1] < warida - i - 1:
			ans += '0'
			ind = yyy[ind] + 1
		else:
			ans += '1'
			ind = xxx[ind] + 1
	print(ans)


for _ in range(int(input())):
	s = input()
	ccc0 = 0
	ccc1 = 0
	c = []
	g = -1
	for zz in range(len(s) - 2, -1, -1):
		if s[zz] == '1':
			ccc1 += 1
			if s[zz + 1] == '1':
				g = '0'
				c.append([g, ccc1 + 1, ccc0])
			else:
				c.append([g, ccc1, ccc0 + 1])
		else:
			ccc0 += 1
			if s[zz + 1] == '0':
				g = '1'
				c.append([g, ccc1, ccc0 + 1])
			else:
				c.append([g, ccc1 + 1, ccc0])
	if s[-1] == '0':
		ccc0 += 1
	else:
		ccc1 += 1
	if ccc0 == 0:
		print(0)
	elif ccc1 == 0:
		print(1)
	else:
		while True:
			if s[0] == '0':
				s = s[:0] + s[1:]
			else:
				break
		b = '1'
		pos0 = -1
		pos1 = -1
		i = 1
		j = 1
		start = 1
		while i < len(s) and j < len(s):
			while i < len(s):
				flag = 0
				if s[i] == '0':
					flag = 1
					pos0 = i
					break
				i += 1
			while j < len(s):
				ff = 0
				if s[j] == '1':
					ff = 1
					pos1 = j
					break
				j += 1
			if flag == 0:
				b += '0'
				break
			elif ff == 0:
				b += '1'
				break
			elif abs(pos1 - pos0) == 1:
				if pos0 > pos1:
					b += '0'
					i = pos0 + 1
					j = pos0 + 1
				elif pos1 == len(s) - 1:
					b += '0'
					i = pos0 + 1
					j = pos0 + 1
				else:
					qq0 = 0
					qq1 = 0
					if c[len(s) - 2 - pos0][0] == '1':
						b += '1'
						i = pos1 + 1
						j = pos1 + 1
					elif c[len(s) - pos0 - 2][0] == '0':
						b += '0'
						i = pos0 + 1
						j = pos0 + 1
					elif c[len(s) - pos0 - 2][0] == -1:
						if c[len(s) - pos0 - 2][1] <= c[len(s) - pos0 - 2][2]:
							b += '0'
							i = pos0 + 1
							j = pos0 + 1
						else:
							b += '1'
							i = pos1 + 1
							j = pos1 + 1
			elif pos0 > pos1:
				b += '0'
				i = pos0 + 1
				j = pos0 + 1
			else:
				b += '1'
				i = pos1 + 1
				j = pos1 + 1
		if i == len(s) and j == len(s):
			b += '0'
		print(b)