Chef has two binary strings A and B, each of length N.

Chef can rearrange both the strings in any way. Find the maximum [bitwise XOR] he can achieve if he rearranges the strings optimally.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of two lines:
- The first line of each test case contains binary string A.
- The second line of each test case contains binary string B.

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

For each test case, output the maximum bitwise XOR of the strings in binary representation.

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

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 5 \cdot 10^{5}$
- Strings $A$ and $B$ consist only of $0$ and $1$.
- The sum of $N$ over all test cases do not exceed $5 \cdot 10^{5}$.

----- Sample Input 1 ------ 
4
0011
1011
100
100
11111
11101
1
0

----- Sample Output 1 ------ 
1110
110
10000
1

----- explanation 1 ------ 
Test case $1$: Rearranging string $A$ as $0011$ and string $B$ as $1101$, the XOR of the strings is $0011\oplus 1101 = 1110$. It can be shown that this is the maximum XOR that can be achieved by rearranging the strings.

Test case $2$: Rearranging string $A$ as $010$ and string $B$ as $100$, the XOR of the strings is $010\oplus 100 = 110$. It can be shown that this is the maximum XOR that can be achieved by rearranging the strings.

Test case $3$: Rearranging string $A$ as $11111$ and string $B$ as $01111$, the XOR of the strings is $11111\oplus 01111 = 10000$. It can be shown that this is the maximum XOR that can be achieved by rearranging the strings.

Test case $4$: Rearranging string $A$ as $1$ and string $B$ as $0$, the XOR of the strings is $1\oplus 0 = 1$. It can be shown that this is the maximum XOR that can be achieved by rearranging the strings.

Difficulty: EASY
Tags: String algorithms

Data structures

Greedy algorithms
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	s1 = input()
	s2 = input()
	s3 = s1 + s2
	a = s3.count('1')
	b = s3.count('0')
	m = min(a, b)
	print('1' * m + '0' * (len(s1) - m))


for i in range(int(input())):
	a = input()
	b = input()
	s = 0
	k = 0
	for i in range(len(a)):
		if a[i] == '0':
			s += 1
		else:
			k += 1
		if b[i] == '0':
			s += 1
		else:
			k += 1
	m = min(s, k)
	res = ''
	for i in range(0, m):
		res += '1'
	for i in range(m, len(a)):
		res += '0'
	print(res)


for i in range(int(input())):
	a = input()
	b = input()
	s = o = 0
	for i in range(len(a)):
		if a[i] == '0':
			s += 1
		else:
			o += 1
		if b[i] == '0':
			s += 1
		else:
			o += 1
	m = min(s, o)
	sr = ''
	for i in range(0, m):
		sr += '1'
	for i in range(m, len(a)):
		sr += '0'
	print(sr)


n = int(input())
for _ in range(n):
	s1 = input()
	s2 = input()
	z1 = 0
	o1 = 0
	for i in s1:
		if i == '0':
			z1 += 1
		else:
			o1 += 1
	z2 = 0
	o2 = 0
	for i in s2:
		if i == '0':
			z2 += 1
		else:
			o2 += 1
	ons = min(z1, o2) + min(o1, z2)
	anss = ''
	for i in range(len(s1)):
		if ons > 0:
			anss += '1'
		else:
			anss += '0'
		ons -= 1
	print(anss)


for i in range(int(input())):
	a = input()
	b = input()
	x = min(a.count('0'), b.count('1')) + min(a.count('1'), b.count('0'))
	p = str(1) * x
	q = str(0) * (len(a) - x)
	print(f'{p}{q}')


for i in range(int(input())):
	x = input()
	y = input()
	a = x + y
	b = min(a.count('0'), a.count('1'))
	c = len(x) - b
	print('1' * b + '0' * c)


for _ in range(int(input())):
	a = input()
	b = input()
	num_of_one_a = a.count('1')
	num_of_zero_a = len(a) - num_of_one_a
	num_of_one_b = b.count('1')
	num_of_zero_b = len(a) - num_of_one_b
	num_of_one_res = min(num_of_one_a, num_of_zero_b) + min(num_of_zero_a, num_of_one_b)
	for one in range(num_of_one_res):
		print('1', end='')
	for zero in range(len(a) - num_of_one_res):
		print('0', end='')
	print()


for _ in range(int(input())):
	a = input()
	b = input()
	zeros = a.count('0') + b.count('0')
	ones = a.count('1') + b.count('1')
	m = min(ones, zeros)
	l = len(a) - m
	for i in range(m):
		print('1', end='')
	for i in range(l):
		print('0', end='')
	print('')


for i in range(int(input())):
	a = input()
	b = input()
	a_len = len(a)
	a_0 = a.count('0')
	a_1 = a.count('1')
	b_0 = b.count('0')
	b_1 = b.count('1')
	string = ''
	c1 = min(a_0, b_1)
	c2 = min(a_1, b_0)
	c = c1 + c2
	for i in range(c):
		string += '1'
	nn = a_len - c
	for i in range(nn):
		string += '0'
	print(string)


for _ in range(int(input())):
	sa = input()
	sb = input()
	c = 0
	s = ''
	sa1 = sa.count('1')
	sa0 = sa.count('0')
	sb1 = sb.count('1')
	sb0 = sb.count('0')
	c = c + min(sa1, sb0)
	c = c + min(sa0, sb1)
	for i in range(c):
		s = s + '1'
	for j in range(len(sa) - c):
		s = s + '0'
	print(s)


for _ in range(int(input())):
	a = input()
	b = input()
	n = len(a)
	a0 = a.count('0')
	a1 = a.count('1')
	b0 = b.count('0')
	b1 = b.count('1')
	rez = '1' * min(a0, b1) + '1' * min(a1, b0) + '0' * (n - len('1' * min(a0, b1) + '1' * min(a1, b0)))
	print(rez)


t = int(input())
for _ in range(t):
	a = input()
	b = input()
	(c0, c1) = (0, 0)
	for i in range(len(a)):
		if a[i] == '0':
			c0 += 1
		elif a[i] == '1':
			c1 += 1
		if b[i] == '0':
			c0 += 1
		elif b[i] == '1':
			c1 += 1
	mn = min(c0, c1)
	print('1' * mn + '0' * (len(a) - mn))


for _ in range(int(input())):
	S1 = input()
	S2 = input()
	count_0 = S1.count('0') + S2.count('0')
	count_1 = S1.count('1') + S2.count('1')
	res = '1' * min(count_0, count_1)
	res += '0' * (len(S1) - len(res))
	print(res)


T = int(input())
for tc in range(T):
	a = input()
	b = input()
	if len(a) > len(b):
		b = '0' * (len(a) - len(b)) + b
	elif len(a) < len(b):
		a = '0' * (len(b) - len(a)) + a
	a0 = a.count('0')
	a1 = a.count('1')
	b0 = b.count('0')
	b1 = b.count('1')
	for i in range(len(a)):
		if a1 > 0 and b0 > 0:
			a1 -= 1
			b0 -= 1
			print('1', end='')
		elif a0 > 0 and b1 > 0:
			a0 -= 1
			b1 -= 1
			print('1', end='')
		elif a0 > 0 and b0 > 0:
			a0 -= 1
			b0 -= 1
			print('0', end='')
		elif a1 > 0 and b1 > 0:
			a1 -= 1
			b1 -= 1
			print('0', end='')
		else:
			pass
	print('')


T = int(input())
while T > 0:
	S1 = input()
	S2 = input()
	count = [0, 0]
	for i in S1:
		count[int(i)] += 1
	for i in S2:
		count[int(i)] += 1
	result = '1' * min(count)
	result += '0' * (len(S1) - min(count))
	print(result)
	T = T - 1


T = int(input())
for i in range(T):
	s = 0
	o = 0
	A = input()
	B = input()
	for j in range(len(A)):
		if A[j] == '0':
			o = o + 1
		else:
			s = s + 1
		if B[j] == '0':
			o = o + 1
		else:
			s = s + 1
	m = min(s, o)
	str = ''
	for k in range(0, m):
		str = str + '1'
	for k in range(m, len(A)):
		str = str + '0'
	print(str)


for _ in range(int(input())):
	s1 = input()
	s2 = input()
	s1_1 = s1.count('1')
	s2_1 = s2.count('1')
	n = len(s1)
	sum = min(s1_1, n - s2_1) + min(n - s1_1, s2_1)
	res = '1' * sum + '0' * (n - sum)
	print(res)


for i in range(int(input())):
	s1 = input()
	s2 = input()
	s3 = ''
	s3 = s1 + s2
	one = s3.count('1')
	zero = s3.count('0')
	min1 = min(one, zero)
	st = min1 * '1' + (len(s1) - min1) * '0'
	print(st)


for i in range(int(input())):
	a = input()
	b = input()
	a0 = a.count('0')
	a1 = a.count('1')
	b0 = b.count('0')
	b1 = b.count('1')
	r = min(a1, b0) + min(a0, b1)
	print(r * '1' + (len(a) - r) * '0')


t = int(input())
while t > 0:
	a = input()
	b = input()
	s = 0
	p = a.count('1') + b.count('1')
	q = a.count('0') + b.count('0')
	m = min(p, q)
	s = m * '1' + (len(a) - m) * '0'
	print(s)
	t -= 1


for qwerty in range(int(input())):
	h = input()
	i = input()
	m = 0
	n = 0
	for s in range(len(h)):
		if h[s] == '1':
			m = m + 1
		else:
			n = n + 1
		if i[s] == '1':
			m = m + 1
		else:
			n = n + 1
	for s in range(min(n, m)):
		print('1', end='')
	for s in range(min(n, m), len(h)):
		print('0', end='')
	print()


T = int(input())
for _ in range(T):
	a = input()
	b = input()
	s = ''
	aa = a.count('1')
	bb = b.count('1')
	m = aa + bb
	a0 = a.count('0')
	b0 = b.count('0')
	n = a0 + b0
	minimum = min(m, n)
	for i in range(minimum):
		s += '1'
	for i in range(minimum, len(a)):
		s += '0'
	print(s)


for kp in range(int(input())):
	one = input()
	two = input()
	aa = one.count('1')
	bb = two.count('1')
	cc = one.count('0')
	dd = two.count('0')
	th = aa + bb
	hb = cc + dd
	gg = ''
	kk = min(th, hb)
	hh = '1' * kk
	gg = gg + hh
	while len(gg) < len(one):
		gg = gg + '0'
	print(gg)


for _ in range(int(input())):
	a = input()
	b = input()
	aa = a.count('1')
	bb = b.count('1')
	cc = a.count('0')
	dd = b.count('0')
	d = aa + bb
	c = cc + dd
	m = min(c, d)
	s = ''
	for i in range(m):
		s += '1'
	for i in range(m, len(a)):
		s += '0'
	print(s)


t = int(input())
for i in range(t):
	a = input()
	b = input()
	a1 = sorted(a)
	b1 = sorted(b)
	a1 = ''.join(a1)
	b1 = ''.join(b1)
	b2 = b1[::-1]
	d = [ord(a) ^ ord(b) for (a, b) in zip(a1, b2)]
	d = map(str, d)
	f = ''.join(d)
	f = sorted(f, reverse=True)
	f1 = ''.join(f)
	print(f1)


t = int(input())
for i in range(t):
	a = input()
	b = input()
	if a.count('1') == b.count('0'):
		print('1' * len(a))
	else:
		print('1' * (min(a.count('1'), b.count('0')) + min(a.count('0'), b.count('1'))) + '0' * (len(a) - (min(a.count('1'), b.count('0')) + min(a.count('0'), b.count('1')))))


t = int(input())
for tc in range(t):
	a = input()
	b = input()
	l = ''
	k = ''
	c = a.count('0') + b.count('0')
	d = a.count('1') + b.count('1')
	m = min(c, d)
	n = len(a) - m
	for j in range(m):
		l += '1'
	for j in range(n):
		k += '0'
	print(l + k)


for _ in range(int(input())):
	a = input()
	b = input()
	n = len(a)
	c0 = a.count('0') + b.count('0')
	c1 = a.count('1') + b.count('1')
	res = ''
	m = min(c1, c0)
	res += '1' * m
	res += '0' * (n - m)
	print(res)


for _ in range(int(input())):
	s1 = input()
	s2 = input()
	z = s1.count('0') + s2.count('0')
	o = s1.count('1') + s2.count('1')
	m = min(z, o)
	l = len(s1) - m
	for i in range(m):
		print('1', end='')
	for i in range(l):
		print('0', end='')
	print('')


for _ in range(int(input())):
	A = input()
	B = input()
	one = A.count('1') + B.count('1')
	zero = A.count('0') + B.count('0')
	m = min(one, zero)
	print('1' * m + '0' * (len(A) - m))


t = int(input())
while t > 0:
	a = input()
	b = input()
	a0 = a.count('0')
	a1 = len(a) - a0
	b0 = b.count('0')
	b1 = len(b) - b0
	x = min(a0, b1)
	y = min(a1, b0)
	for i in range(x + y):
		print(1, end='')
	for i in range(len(a) - (x + y)):
		print(0, end='')
	print()
	t -= 1


for i in range(int(input())):
	a = input()
	b = input()
	zero = a.count('0') + b.count('0')
	one = a.count('1') + b.count('1')
	x = min(zero, one)
	y = len(a) - x
	for i in range(x):
		print('1', end='')
	for i in range(y):
		print('0', end='')
	print('')


banyak_kasus = int(input())

def BanyakNolDanSatu(biner):
	banyak = [0, 0]
	for x in biner:
		if x == '0':
			banyak[0] += 1
		else:
			banyak[1] += 1
	return banyak

def JadiString(biner):
	hasil = ''
	for x in range(len(biner)):
		hasil += str(biner[x])
	return hasil
while banyak_kasus > 0:
	A = input()
	B = input()
	banyakNolDanSatuDiA = BanyakNolDanSatu(A)
	banyakNolDanSatuDiB = BanyakNolDanSatu(B)
	(banyakNolDiA, banyakSatuDiA) = (banyakNolDanSatuDiA[0], banyakNolDanSatuDiA[1])
	(banyakNolDiB, banyakSatuDiB) = (banyakNolDanSatuDiB[0], banyakNolDanSatuDiB[1])
	total = len(A) + len(B)
	k = max(banyakNolDiA + banyakNolDiB, banyakSatuDiA + banyakSatuDiB)
	banyakSatuDiKanan = total - k
	hasilXOR = [0 for x in range(total // 2)]
	for x in range(banyakSatuDiKanan):
		hasilXOR[x] = 1
	print(JadiString(hasilXOR))
	banyak_kasus -= 1


tc = int(input())
for _ in range(tc):
	a = list(input())
	b = list(input())
	n = len(a)
	s = 0
	for i in range(n):
		if a[i] == '1':
			s += 1
		if b[i] == '1':
			s += 1
	d = ''
	if s <= n:
		for j in range(s):
			d += '1'
		for j in range(n - s):
			d += '0'
	else:
		s = s - 2 * (s - n)
		for j in range(s):
			d += '1'
		for j in range(n - s):
			d += '0'
	print(d)


T = int(input())
for i in range(T):
	A = list(input())
	B = list(input())
	M = []
	P1 = A.count('0')
	P2 = A.count('1')
	P3 = B.count('0')
	P4 = B.count('1')
	S1 = P1 + P3
	S2 = P2 + P4
	S = min(S1, S2)
	for j in range(0, S):
		M.append('1')
	for k in range(len(A) - S):
		M.append('0')
	print(''.join(M))


for i in range(int(input())):
	a = input()
	b = input()
	n = len(a)
	x = a.count('1') + b.count('1')
	y = a.count('0') + b.count('0')
	d = min(x, y)
	s = d * '1' + (n - d) * '0'
	print(s)


for _ in range(int(input())):
	a = input()
	b = input()
	a1 = a.count('1')
	a0 = a.count('0')
	b1 = b.count('1')
	b0 = b.count('0')
	n = len(a)
	if a1 + b1 < n:
		n1 = a1 + b1
	else:
		n1 = 2 * n - (a1 + b1)
	n0 = n - n1
	ans = ['1'] * n1 + ['0'] * n0
	print(''.join(ans))


t = int(input())
while t > 0:
	t -= 1
	a = input()
	b = input()
	c = a + b
	o = z = 0
	for i in range(len(c)):
		if c[i] == '0':
			z += 1
		else:
			o += 1
	j = min(o, z)
	s = ''
	for i in range(0, j):
		s += '1'
	for i in range(j, len(a)):
		s += '0'
	print(s)


for i in range(0, int(input())):
	a = list(input())
	a = [int(i) for i in a]
	b = list(input())
	b = [int(i) for i in b]
	c1 = 0
	s0 = 0
	for i in range(0, len(a)):
		if a[i] == 1:
			c1 += 1
		if b[i] == 0:
			s0 += 1
	c0 = len(a) - c1
	s1 = len(b) - s0
	f = []
	f1 = min(c1, s0)
	f2 = min(c0, s1)
	fn = f1 + f2
	stw = []
	for i in range(0, fn):
		stw.append('1')
	for i in range(0, len(a) - fn):
		stw.append('0')
	sttt = ''.join(map(str, stw))
	print(sttt)


t = int(input())
while t != 0:
	a = input()
	b = input()
	oa = 0
	za = 0
	ob = 0
	zb = 0
	for x in a:
		if x == '1':
			oa += 1
		else:
			za += 1
	for x in b:
		if x == '1':
			ob += 1
		else:
			zb += 1
	n = len(a)
	onec = min(za, ob)
	onec += min(zb, oa)
	zeroc = n - onec
	ans = '1' * onec + '0' * zeroc
	print(ans)
	t -= 1


t = int(input())
for i in range(t):
	s1 = list(input())
	s2 = list(input())
	z1 = s1.count('0')
	o1 = s1.count('1')
	z2 = s2.count('0')
	o2 = s2.count('1')
	n = min(z1, o2) + min(o1, z2)
	l = []
	for j in range(n):
		l.append('1')
	for j in range(len(s1) - n):
		l.append('0')
	for j in l:
		print(j, end='')
	print('\n')


t = int(input())
for i in range(t):
	a = input()
	b = input()
	z = a.count('0') + b.count('0')
	o = a.count('1') + b.count('1')
	m = min(z, o)
	l = len(a) - m
	for i in range(m):
		print(1, end='')
	for i in range(l):
		print(0, end='')
	print()


t = int(input())
while t != 0:
	a = input()
	b = input()
	a1 = 0
	a0 = 0
	b1 = 0
	b0 = 0
	str = ''
	dif = 0
	for i in range(len(a)):
		if a[i] == '1':
			a1 += 1
		else:
			a0 += 1
		if b[i] == '1':
			b1 += 1
		else:
			b0 += 1
	dif = min(a0, b1) + min(a1, b0)
	for j in range(dif):
		str += '1'
	for i in range(len(a) - dif):
		str += '0'
	print(str)
	t -= 1


t = int(input())
while t > 0:
	a = input()
	b = input()
	ans = ''
	n1 = a.count('1') + b.count('1')
	n0 = a.count('0') + b.count('0')
	n = min(n1, n0)
	for i in range(len(a)):
		if n > 0:
			ans += '1'
			n = n - 1
		else:
			ans += '0'
	print(ans)
	t = t - 1


for tc in range(int(input())):
	s1 = input()
	s2 = input()
	kmap = {'0': 0, '1': 0}
	count = 0
	res = ''
	for ele in s1:
		kmap[ele] += 1
	for ele in s2:
		if ele == '1':
			if kmap['0'] > 0:
				kmap['0'] -= 1
				res += '1'
			else:
				count += 1
		elif kmap['1'] > 0:
			kmap['1'] -= 1
			res += '1'
		else:
			count += 1
	count = count + kmap['1'] + kmap['0']
	for i in range(count // 2):
		res += '0'
	print(res)


for i in range(int(input())):
	s1 = input()
	s2 = input()
	x = s1.count('0') + s2.count('0')
	y = s1.count('1') + s2.count('1')
	m = min(x, y)
	l = len(s1) - m
	for i in range(m):
		print('1', end='')
	for i in range(l):
		print('0', end='')
	print('')


import sys
for _ in range(int(input())):
	a = input()
	b = input()
	n = len(a)
	na = a.count('0')
	nb = b.count('0')
	c = min(na, n - nb) + min(nb, n - na)
	print('1' * c + '0' * (n - c))


for _ in range(int(input())):
	a = input()
	b = input()
	c = min(a.count('0'), b.count('1')) + min(b.count('0'), a.count('1'))
	print('1' * c + '0' * (len(a) - c))


v = int(input())
i = []
for th in range(0, v):
	yt = str(input())
	mk = str(input())
	yn = [yt, mk]
	i.append(yn)
for kkm in i:
	jk = kkm[0]
	iio = kkm[1]
	pt = 0
	ikl = 0
	for iil in iio:
		if iil == '0':
			ikl += 1
		else:
			pt += 1
	lmb = 0
	mjt = 0
	for hh in jk:
		if hh == '1':
			lmb += 1
		else:
			mjt += 1
	pmrew = ''
	while lmb != 0:
		if lmb != 0:
			lmb -= 1
			if ikl != 0:
				ikl -= 1
				pmrew += '1'
			else:
				break
	while pt != 0:
		if pt != 0:
			pt -= 1
			if mjt != 0:
				mjt -= 1
				pmrew += '1'
			else:
				break
	ikew = len(jk) - len(pmrew)
	for mje in range(0, ikew):
		pmrew += '0'
	print(pmrew)


for i in range(int(input())):
	a = input()
	b = input()
	a0 = a.count('0')
	a1 = a.count('1')
	b0 = b.count('0')
	b1 = b.count('1')
	for i in range(len(a)):
		if a0 > 0 and b1 > 0:
			a0 -= 1
			b1 -= 1
			print('1', end='')
		elif a1 > 0 and b0 > 0:
			a1 -= 1
			b0 -= 1
			print('1', end='')
		elif a0 > 0 and b0 > 0:
			a0 -= 1
			b0 -= 1
			print('0', end='')
		elif a1 > 0 and b1 > 0:
			a1 -= 1
			b1 -= 1
			print('0', end='')
	print()


for _ in range(int(input())):
	a = input()
	b = input()
	(c1, c2) = (0, 0)
	for i in range(len(a)):
		if a[i] == '0':
			c1 += 1
		if a[i] == '1':
			c2 += 1
		if b[i] == '0':
			c1 += 1
		if b[i] == '1':
			c2 += 1
	m = min(c1, c2)
	ans = ''
	for i in range(m):
		ans += '1'
	for i in range(m, len(a)):
		ans += '0'
	print(ans)


def main():
	T = int(input())
	for _ in range(T):
		A = input()
		B = input()
		(one, zero) = (0, 0)
		for x in range(len(A)):
			if A[x] == '1':
				one += 1
			else:
				zero += 1
			if B[x] == '1':
				one += 1
			else:
				zero += 1
		rg = min(one, zero)
		for i in range(rg):
			print('1', end='')
		for i in range(rg, len(A)):
			print('0', end='')
		print()
main()


def main():
	T = int(input())
	for _ in range(T):
		A = input()
		B = input()
		rg = min(A.count('1') + B.count('1'), A.count('0') + B.count('0'))
		for i in range(rg):
			print('1', end='')
		for i in range(rg, len(A)):
			print('0', end='')
		print()
main()


t = int(input())
for i in range(t):
	a = input()
	b = input()
	n = min(a.count('0'), b.count('1')) + min(b.count('0'), a.count('1'))
	print('1' * n + '0' * (len(a) - n))


for _ in range(int(input())):
	(a, b) = (input(), input())
	a1 = a0 = 0
	b1 = b0 = 0
	for i in a:
		a1 += i == '1'
		a0 += i == '0'
	for i in b:
		b1 += i == '1'
		b0 += i == '0'
	max_diff = min(a1, b0) + min(a0, b1)
	ans = '1' * max_diff
	ans += '0' * (len(a) - len(ans))
	print(ans)


t = int(input())
for l in range(t):
	c = input()
	d = input()
	l1 = []
	l2 = []
	l3 = []
	for i in c:
		l1.append(i)
	for j in d:
		l2.append(j)
	l1.sort()
	l2.sort(reverse=True)
	for k in range(len(l1)):
		if l1[k] == l2[k]:
			l3.append(0)
		else:
			l3.append(1)
	l3.sort(reverse=True)
	for m in l3:
		print(m, end='')
	print()


from collections import Counter
t = int(input())
for _ in range(t):
	x = input()
	y = input()
	xd = Counter(x)
	yd = Counter(y)
	res = ''
	ones = min(xd['0'], yd['1']) + min(xd['1'], yd['0'])
	if ones >= len(x):
		while ones:
			res += '1'
			ones -= 1
	elif ones < len(x):
		zeros = len(x) - ones
		while ones:
			res += '1'
			ones -= 1
		while zeros:
			res += '0'
			zeros -= 1
	print(res)


t = int(input())
for t in range(t):
	a = input()
	b = input()
	a_1 = a.count('1')
	a_0 = a.count('0')
	b_1 = b.count('1')
	b_0 = b.count('0')
	res = min(a_1, b_0) + min(a_0, b_1)
	s = ''
	for i in range(res):
		s += str(1)
	for i in range(res, len(a)):
		s += str(0)
	print(s)


t = int(input())
while t:
	a = str(input())
	b = str(input())
	ans = ''
	a0 = 0
	a1 = 0
	b0 = 0
	b1 = 0
	for x in a:
		if x == '0':
			a0 += 1
		else:
			a1 += 1
	for x in b:
		if x == '0':
			b0 += 1
		else:
			b1 += 1
	if a0 > b1:
		c1 = b1
	else:
		c1 = a0
	if a1 > b0:
		c2 = b0
	else:
		c2 = a1
	c4 = c1 + c2
	c3 = a0 + a1 - c4
	ans = '1' * c4 + '0' * c3
	print(ans)
	t -= 1


for i in range(int(input())):
	a = input()
	b = input()
	one = a.count('1') + b.count('1')
	zero = a.count('0') + b.count('0')
	c = min(one, zero)
	e = ''
	for j in range(0, c):
		e += '1'
	for k in range(c, len(a)):
		e += '0'
	print(e)


for i in range(int(input())):
	a = input()
	b = input()
	o = z = 0
	for i in range(len(a)):
		if a[i] == '0':
			z += 1
		else:
			o += 1
		if b[i] == '0':
			z += 1
		else:
			o += 1
	s = min(o, z)
	st = ''
	for i in range(0, s):
		st += '1'
	for i in range(s, len(a)):
		st += '0'
	print(st)


def count(x):
	temp = 0
	for i in x:
		if i == '1':
			temp = temp + 1
	return temp

def ans(x, y):
	c1 = count(x)
	c2 = count(y)
	res = ''
	if c1 + c2 <= len(x):
		for _ in range(c1 + c2):
			res = res + '1'
		for _ in range(len(x) - (c1 + c2)):
			res = res + '0'
	else:
		n = 2 * len(x) - (c1 + c2)
		for _ in range(n):
			res = res + '1'
		for _ in range(len(x) - n):
			res = res + '0'
	return res
t = int(input())
for _ in range(t):
	x = input()
	y = input()
	print(ans(x, y))