Recently, Chef studied the binary numeral system and noticed that it is extremely simple to perform bitwise operations like AND, XOR or bit shift on non-negative integers, while it is much more complicated to perform arithmetic operations (e.g. addition, multiplication or division).
After playing with binary operations for a while, Chef invented an interesting algorithm for addition of two non-negative integers $A$ and $B$:
function add(A, B):
while B is greater than 0:
U = A XOR B
V = A AND B
A = U
B = V * 2
return A

Now Chef is wondering how fast this algorithm is. Given the initial values of $A$ and $B$ (in binary representation), he needs you to help him compute the number of times the while-loop of the algorithm is repeated.

-----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 line of each test case contains a single string $A$.
- The second line contains a single string $B$.

-----Output-----
For each test case, print a single line containing one integer ― the number of iterations the algorithm will perform during addition of the given numbers $A$ and $B$.

-----Constraints-----
- $1 \le T \le 10^5$
- $1 \le |A|, |B| \le 10^5$
- $A$ and $B$ contain only characters '0' and '1'
- the sum of $|A| + |B|$ over all test cases does not exceed $10^6$

-----Subtasks-----
Subtask #1 (20 points): $|A|, |B| \le 30$
Subtask #2 (30 points):
- $|A|, |B| \le 500$
- the sum of $|A| + |B|$ over all test cases does not exceed $10^5$
Subtask #3 (50 points): original constraints

-----Example Input-----
3
100010
0
0
100010
11100
1010

-----Example Output-----
0
1
3

-----Explanation-----
Example case 1: The initial value of $B$ is $0$, so while-loop is not performed at all.
Example case 2: The initial values of $A$ and $B$ are $0_2 = 0$ and $100010_2 = 34$ respectively. When the while-loop is performed for the first time, we have:
- $U = 34$
- $V = 0$
- $A$ changes to $34$
- $B$ changes to $2 \cdot 0 = 0$
The while-loop terminates immediately afterwards, so it is executed only once.
Example case 3: The initial values of $A$ and $B$ are $11100_2 = 28$ and $1010_2 = 10$ respectively. After the first iteration, their values change to $22$ and $16$ respectively. After the second iteration, they change to $6$ and $32$, and finally, after the third iteration, to $38$ and $0$.

Difficulty: MEDIUM_HARD
Tags: String algorithms

Bit manipulation

Data structures

Mathematics
Skill types: Bit manipulation

Data structures

Starter code:

Solutions:
for t in range(int(input())):
	(a, b) = (input(), input())
	if int(b, 2) == 0:
		print(0)
		continue
	l = max(len(a), len(b)) + 1
	(a, b) = (a.rjust(l, '0'), b.rjust(l, '0'))
	(p, ans, c) = ('0', 0, 0)
	for i in range(1, l + 1):
		if p == '1':
			c += 1
			ans = max(ans, c)
			if a[-i] == b[-i]:
				c = 0
		else:
			c = 0
		p = '1' if (a[-i] + b[-i] + p).count('1') > 1 else '0'
	print(ans + 1)


__author__ = 'Ronald Kaiser'
__email__ = 'raios dot catodicos at gmail dot com'
from sys import stdin, stdout
rline = lambda : stdin.readline().strip()

def solve():
	global A, B
	if not '1' in B:
		return 0
	diff = len(A) - len(B)
	if diff > 0:
		B = '0' * diff + B
	else:
		A = '0' * -diff + A
	s = 1
	for i in range(len(A) - 1, -1, -1):
		if A[i] == B[i] == '1':
			j = i - 1
			while j >= 0 and A[j] != B[j]:
				j -= 1
			s = max(s, i - j + 1)
	return s

def read_input():
	global A, B
	(A, B) = ('0' + rline(), '0' + rline())

def write_output(s):
	stdout.write('\n'.join(map(str, s)))

def main():
	s = []
	for _ in range(int(input())):
		read_input()
		answer = solve()
		s.append(answer)
	write_output(s)
main()


t = int(input())
for i in range(t):
	a1 = input()
	b1 = input()
	val1 = 0
	val2 = 0
	c = 0
	u = 0
	v = 0
	val1 = int(a1, 2)
	val2 = int(b1, 2)
	while val2 > 0:
		c += 1
		u = val1 ^ val2
		v = val1 & val2
		val1 = u
		val2 = 2 * v
	print(c)


t = int(input())
while t > 0:
	t -= 1
	a = input()
	b = input()
	k = int(b, 2)
	if k == 0:
		print(0)
		continue
	c = ''
	if len(a) > len(b):
		b = c.zfill(len(a) - len(b)) + b
	else:
		a = c.zfill(len(b) - len(a)) + a
	mx = 1
	i = len(a) - 1
	while i >= 0:
		s = -1
		if a[i] == '1' and b[i] == '1':
			s = i
			j = i - 1
			e = -1
			while j >= 0:
				if a[j] == '1' and b[j] == '1' or (a[j] == '0' and b[j] == '0'):
					e = j
					break
				j -= 1
			i = j
			if s - e + 1 > mx:
				mx = s - e + 1
		else:
			i -= 1
	j = 0
	if s > -1 and e == -1:
		e = j - 1
		if s - e + 1 > mx:
			mx = s - e + 1
	print(mx)


for _ in range(int(input())):
	(A, B, count, res, flag) = (str(input()), str(input()), 0, 1, 0)
	if int(B) == 0:
		print(0)
	else:
		(A, B) = (A.zfill(max(len(A), len(B))), B.zfill(max(len(A), len(B))))
		for (i, j) in zip(A[::-1], B[::-1]):
			if i == j:
				if i == '1':
					(flag, count) = (1, 1)
				elif i == '0' and j == '0':
					(count, flag) = (0, 0)
			elif flag == 1:
				count += 1
			res = max(res, count + 1)
		print(res)


for _ in range(int(input())):
	a = input()
	b = input()
	if b == '0':
		print(0)
	elif b != '0':
		if len(b) > len(a):
			d = len(b) - len(a)
			for i in range(d):
				a = '0' + a
		elif len(a) > len(b):
			d = len(a) - len(b)
			for i in range(d):
				b = '0' + b
		a = '0' + a
		b = '0' + b
		la = len(a) - 1
		mx = 0
		a = ''.join(reversed(a))
		b = ''.join(reversed(b))
		for i in range(la):
			A = 1
			if a[i] == '1' and b[i] == '1':
				check = 1
				while True:
					if a[check + i] != b[check + i]:
						A += 1
					else:
						break
					check += 1
				if mx < A:
					mx = A
		print(mx + 1)


t = int(input())
for j in range(t):
	a = int(input(), 2)
	b = int(input(), 2)
	i = 0
	while b > 0:
		u = a ^ b
		v = a & b
		a = u
		b = 2 * v
		i += 1
	print(i)


t = int(input())
while t > 0:
	s1 = str(input())
	s2 = str(input())
	t -= 1
	if '1' not in s2:
		print(0)
	else:
		if len(s2) < len(s1):
			for i in range(abs(len(s2) - len(s1))):
				s2 = '0' + s2
		else:
			for i in range(abs(len(s2) - len(s1))):
				s1 = '0' + s1
		s1 = s1[::-1]
		s2 = s2[::-1]
		ans = 0
		tre = 0
		for i in range(len(s1)):
			k1 = s1[i]
			k2 = s2[i]
			if k1 == k2 == '1':
				x = i + 1
				while x < len(s1):
					if s1[x] == s2[x]:
						break
					x += 1
				val = abs(i - x)
				if val > tre:
					ans += abs(val - tre)
					tre = val
		print(ans + 1)


def fn2(a, b):
	print('-' * 30)
	ct = 0
	while b > 0:
		ct += 1
		lenMax = max(len(bin(a)[2:]), len(bin(b)[2:]))
		lena = len(bin(a)[2:])
		lenb = len(bin(b)[2:])
		print('0' * (lenMax - lena) + bin(a)[2:], '\n' + '0' * (lenMax - lenb) + bin(b)[2:], '\n')
		u = a ^ b
		b = (a & b) << 1
		a = u
	lenMax = max(len(bin(a)[2:]), len(bin(b)[2:]))
	lena = len(bin(a)[2:])
	lenb = len(bin(b)[2:])
	print('0' * (lenMax - lena) + bin(a)[2:], '\n' + '0' * (lenMax - lenb) + bin(b)[2:], '\n')
	return ct

def go2():
	for tt in range(int(input())):
		a = int(input(), 2)
		b = int(input(), 2)
		x = fn3(a, b)
		print(x)

def fn3(a, b):
	if b == 0:
		return 0
	elif a == 0:
		return 1
	lenMax = max(len(bin(a)[2:]), len(bin(b)[2:]))
	lena = len(bin(a)[2:])
	lenb = len(bin(b)[2:])
	a = '0' * (lenMax - lena) + bin(a)[2:]
	b = '0' * (lenMax - lenb) + bin(b)[2:]
	a = list(a)
	b = list(b)
	x = []
	for i in range(lenMax):
		x.append(int(a[i]) + int(b[i]))
	maxc = 1
	u = lenMax
	while u > 0:
		u -= 1
		if x[u] == 2:
			c = 2
			while u > 0:
				u -= 1
				if x[u] == 1:
					c += 1
				else:
					u += 1
					break
			if c > maxc:
				maxc = c
	return maxc
go2()


for _ in range(0, int(input())):
	a = input()
	b = input()

	def f(a, b):
		y = 0
		while b > 0:
			u = a ^ b
			v = a & b
			a = u
			b = v * 2
			y += 1
		return y
	print(f(int(a, 2), int(b, 2)))


turn = int(input())
for _ in range(turn):
	flag = 0
	c = 0
	max = -1
	a = input()
	b = input()
	l = len(a) if len(a) > len(b) else len(b)
	a = a.zfill(l)
	b = b.zfill(l)
	if int(b, 2) == 0:
		print(0)
		continue
	m = len(a) - len(b)
	for i in range(len(a), 0, -1):
		if a[i - 1] == '1' and b[i - 1] == '1':
			flag = 1
			if max < c:
				max = c
			c = 0
		elif (a[i - 1] == '1' and b[i - 1] == '0' or (a[i - 1] == '0' and b[i - 1] == '1')) and flag != 0:
			c += 1
			if max < c:
				max = c
		elif a[i - 1] == '0' and b[i - 1] == '0':
			flag = 0
	if max == -1:
		print(1)
	else:
		print(max + 2)


def solve(num1, num2):
	C = int(num1, 2)
	D = int(num2, 2)
	x = C & D
	y = C ^ D
	p = len(num1)
	q = len(num2)
	maxi = 0
	if p > q:
		maxi = p
	else:
		maxi = q
	x = bin(x)[2:].zfill(maxi)
	y = bin(y)[2:].zfill(maxi)
	maxi = 0
	max_till = 0
	if D == 0:
		return '0'
	else:
		for i in range(len(y)):
			if y[i] == '1' and x[i] == '0':
				maxi = maxi + 1
				continue
			elif y[i] == '0' and x[i] == '0':
				maxi = 0
			elif y[i] == '0' and x[i] == '1':
				max_till = max(max_till, maxi)
				maxi = 0
		if max_till == 0 and x.count('1') > 0:
			return '2'
		elif max_till == 0 and x.count('1') == 0:
			return '1'
		else:
			return max_till + 2
t = int(input())
while t != 0:
	num1 = input()
	num2 = input()
	print(solve(num1, num2))
	t -= 1


import random

def optimalAns(a, b):
	a = list(a)
	b = list(b)
	count0 = 0
	for i in range(len(b)):
		if b[i] == '0':
			count0 += 1
	if count0 == len(b):
		return 0
	count = 0
	for i in range(len(a)):
		if a[i] == '0':
			count += 1
	if count == len(a):
		return 1
	if len(a) > len(b):
		temp = list(['0'] * (len(a) - len(b))) + list(b)
		b = temp
	elif len(b) > len(a):
		temp = ['0'] * (len(b) - len(a)) + list(a)
		a = temp
	carry = 0
	max_carry = 0
	inCount = False
	for i in range(len(a) - 1, -1, -1):
		if a[i] == b[i] == '1':
			inCount = True
			carry = 1
			max_carry = max(max_carry, carry)
		elif inCount == True and (a[i] == '1' and b[i] == '0' or (a[i] == '0' and b[i] == '1')):
			carry += 1
			max_carry = max(max_carry, carry)
		else:
			inCount = False
			max_carry = max(max_carry, carry)
			carry = 0
	return max_carry + 1
for _ in range(int(input())):
	str1 = str(input())
	str2 = str(input())
	print(optimalAns(str1, str2))


for _ in range(int(input())):
	a = input().strip()
	b = input().strip()
	if len(a) < len(b):
		a = '0' * (len(b) - len(a)) + a
	a = list(a)
	b_ones = []
	for i in range(len(b)):
		if b[i] == '1':
			b_ones.append(len(b) - i)
	iter = 0
	while len(b_ones) != 0:
		new_bones = []
		for bit in b_ones:
			aind = len(a) - bit - iter
			if aind >= 0:
				if a[aind] == '1':
					a[aind] = ('0', new_bones.append(bit))
				else:
					a[aind] = '1'
		b_ones = new_bones
		iter += 1
	print(iter)


import atexit
import io
import sys
from collections import defaultdict
for t in range(0, int(input())):
	a = input()
	b = input()
	if b == '0':
		print(0)
	elif b != '0':
		if len(b) > len(a):
			d = len(b) - len(a)
			for i in range(d):
				a = '0' + a
		elif len(a) > len(b):
			d = len(a) - len(b)
			for i in range(d):
				b = '0' + b
		a = '0' + a
		b = '0' + b
		la = len(a) - 1
		mx = 0
		a = ''.join(reversed(a))
		b = ''.join(reversed(b))
		for i in range(la):
			A = 1
			if a[i] == '1' and b[i] == '1':
				check = 1
				while True:
					if a[check + i] != b[check + i]:
						A += 1
					else:
						break
					check += 1
				if mx < A:
					mx = A
		print(mx + 1)


for _ in range(int(input())):
	a = input()
	b = input()
	if b == '0':
		print(0)
		continue
	la = len(a)
	lb = len(b)
	l = la
	if la > lb:
		b = '0' * (la - lb) + b
	elif la < lb:
		a = '0' * (lb - la) + a
		l = lb
	a = '0' + a
	b = '0' + b
	ans = 0
	count = 0
	for i in range(l, -1, -1):
		if a[i] == '1' and b[i] == '1':
			ans = max(ans, count)
			count = 1
		elif a[i] == '0' and b[i] == '0':
			ans = max(ans, count)
			count = 0
		elif count:
			count += 1
	print(ans + 1)


t = int(input())
for _ in range(t):
	A = input()
	B = input()
	a = int(A, 2)
	b = int(B, 2)
	A = list(A)
	B = list(B)
	ans = 0
	if len(A) > len(B):
		B = B[::-1]
		while len(B) != len(A):
			B.append('0')
		B = B[::-1]
	if len(A) < len(B):
		A = A[::-1]
		while len(A) != len(B):
			A.append('0')
		A = A[::-1]
	B = B[::-1]
	C = []
	A = A[::-1]
	maxx = 0
	if a > 1000000 and b > 10000000:
		for i in range(len(A)):
			C.append(int(A[i]) + int(B[i]))
		for i in range(len(A)):
			if C[i] == 2:
				i += 1
				temp = 0
				while i < len(A) and C[i] == 1:
					temp += 1
					i += 1
				if temp > maxx:
					maxx = temp
			else:
				i += 1
		if b == 0:
			print(0)
		elif a == 0:
			print(1)
		else:
			print(maxx + 2)
	else:
		ans = 0
		while b > 0:
			U = a ^ b
			V = a & b
			b = 2 * V
			a = U
			ans += 1
		print(ans)


for _ in range(int(input())):
	a = '0' + input()
	b = '0' + input()
	n = len(a)
	m = len(b)
	if b == '00':
		print(0)
		continue
	elif a == '00':
		print(1)
		continue
	if n < m:
		a = '0' * (m - n) + a
	elif n > m:
		b = '0' * (n - m) + b
	m = 0
	for i in range(len(a) - 1, 0, -1):
		cnt = 1
		if a[i] == '1' and b[i] == '1':
			j = -1
			while True:
				if a[j + i] != b[j + i]:
					cnt += 1
				else:
					break
				j -= 1
			if m < cnt:
				m = cnt
	print(m + 1)


from collections import Counter
test = int(input())
for intr in range(test):
	arr1 = list(input())
	arr2 = list(input())
	arr1.reverse()
	arr2.reverse()
	if not (len(arr2) == 1 and arr2[0] == '0'):
		value1 = 1
		arr3 = []
		arr4 = []
		minlength = min(len(arr1), len(arr2))
		for i in range(minlength):
			arr3.append(int(arr1[i]) & int(arr2[i]))
			arr4.append(int(arr1[i]) ^ int(arr2[i]))
		for i in range(minlength, len(arr1)):
			arr4.append(int(arr1[i]))
		for i in range(minlength, len(arr2)):
			arr4.append(int(arr2[i]))
		arr5 = []
		for i in range(len(arr3)):
			if arr3[i] == 1:
				arr5.append(i)
		arr6 = [0]
		for i in range(minlength):
			arr6[0] += 1
		j = 0
		for i in range(len(arr5)):
			ans = 2
			for j in range(arr5[i] + 1, len(arr4)):
				if arr4[j] == 1:
					ans += 1
				else:
					break
			value1 = max(value1, ans)
			if j == len(arr4) - 1:
				break
		print(value1)
	else:
		print('0')


for _ in range(int(input())):
	a = '0b' + input()
	b = '0b' + input()
	a = int(a, 2)
	b = int(b, 2)
	cnt = 0
	while b:
		U = a ^ b
		V = a & b
		a = U
		b = V * 2
		cnt += 1
	print(cnt)


from sys import stdin
t = int(stdin.readline())
while t:
	a = stdin.readline().strip()
	b = stdin.readline().strip()
	if b == '0':
		print(0)
	else:
		(la, lb) = (len(a), len(b))
		l = 0
		if la > lb:
			b = '0' * (la - lb) + b
			l = la
		else:
			a = '0' * (lb - la) + a
			l = lb
		(res, i) = (1, l - 1)
		while i >= 0:
			if a[i] == '1' and b[i] == '1':
				j = i - 1
				while j >= 0 and a[j] != b[j]:
					j -= 1
				res = max(res, i - j + 1)
				i = j
			else:
				i -= 1
		print(res)
	t -= 1


def samelength(n, p, ln, lp):
	if lp == ln:
		return (n, p, ln, lp)
	elif lp > ln:
		for _ in range(lp - ln):
			n = '0' + n
		ln = lp
	else:
		for _ in range(ln - lp):
			p = '0' + p
		lp = ln
	return (n, p, ln, lp)

def addb(a, b, c):
	if a == b and b == c and (c == '0'):
		return ('0', '0')
	elif a == b and b == c and (c == '1'):
		return ('1', '1')
	elif a == '0' and b == c and (c == '1'):
		return ('0', '1')
	elif a == '0':
		return ('1', '0')
	elif a == '1' and b == c and (b == '0'):
		return ('1', '0')
	return ('0', '1')

def coans(n, p):
	ln = len(n)
	lp = len(p)
	(n, p, ln, lp) = samelength(n, p, ln, lp)
	carry = ['0']
	ans = 0
	c0 = 0
	for i in range(1, ln + 1):
		(d, f) = addb(carry[-1], n[-i], p[-i])
		carry.append(f)
	n = '0' + n
	p = '0' + p
	for i in range(1, ln + 2):
		if carry[i - 1] == '1':
			c0 += 1
			if carry[i - 1] == '1' and n[-i] == '1' and (p[-i] == '1'):
				ans = max(c0, ans)
				c0 = 0
			if carry[i - 1] == '1' and n[-i] == '0' and (p[-i] == '0'):
				ans = max(c0, ans)
				c0 = 0
		else:
			ans = max(c0, ans)
			c0 = 0
		ans = max(c0, ans)
	return ans + 1
for _ in range(int(input())):
	n = input()
	p = input()
	dp = int(p, base=2)
	if dp == 0:
		print('0')
	else:
		print(coans(n, p))


iterations = int(input())
for x in range(iterations):
	firstValue = input()
	secondValue = input()
	firstValueLength = len(firstValue)
	secondValueLength = len(secondValue)
	One = int(firstValue, 2)
	Two = int(secondValue, 2)
	total = 0
	upper = 0
	if firstValueLength - 1 > 500 or secondValueLength - 1 > 500:
		variable = '0' * abs(firstValueLength - secondValueLength)
		if firstValueLength > secondValueLength:
			secondValue = variable + secondValue
		else:
			firstValue = variable + firstValue
		firstValueArray = firstValue[::-1]
		secondValueArray = secondValue[::-1]
		indicator = 0
		for y in range(len(firstValueArray)):
			if firstValueArray[y] == '0' and secondValueArray[y] == '0':
				indicator = 0
				total = 0
			elif firstValueArray[y] == '1' and secondValueArray[y] == '1':
				indicator = 1
				total = 0
			elif indicator == 1:
				total = total + 1
				if total > upper:
					upper = total
		print(upper + 2)
	else:
		while Two > 0:
			ack = One ^ Two
			xyz = One & Two
			One = ack
			Two = xyz * 2
			total = total + 1
		print(total)


t = int(input())
for i in range(t):
	first_string = input()
	second_string = input()
	if int(second_string, 2) == 0:
		print(0)
	elif int(first_string, 2) == 0:
		print(1)
	else:
		n1 = len(first_string)
		n2 = len(second_string)
		if n1 > n2:
			temp_string = ''
			for j in range(n1 - n2):
				temp_string = temp_string + '0'
			temp_string = temp_string + second_string
			second_string = temp_string
		elif n2 > n1:
			temp_string = ''
			for j in range(n2 - n1):
				temp_string = temp_string + '0'
			temp_string = temp_string + first_string
			first_string = temp_string
		x = len(first_string) - 1
		compare_variable = -1
		while x >= 0:
			temp_count = 0
			if first_string[x] == '1' and second_string[x] == '1':
				x -= 1
				while first_string[x] != second_string[x] and x >= 0:
					temp_count += 1
					x -= 1
				if temp_count > compare_variable:
					compare_variable = temp_count
			else:
				x -= 1
		if compare_variable == -1:
			print(1)
		else:
			print(compare_variable + 2)


def test(a, b):
	if int(b) == 0:
		return 0
	l = max(len(a), len(b))
	st_a = len(a)
	st_b = len(b)
	s = '0' * 10 ** 5
	if st_a > st_b:
		b = s[:st_a - st_b] + b
	else:
		a = s[:st_b - st_a] + a
	a = a[::-1]
	b = b[::-1]
	i = 0
	ans = 1
	while i < l:
		if a[i] == '1' and b[i] == '1':
			j = i + 1
			while j < l and a[j] != b[j]:
				j += 1
			ans = max(ans, j - i + 1)
			i = j - 1
		i += 1
	return ans
t = int(input())
while t:
	t -= 1
	a = input()
	b = input()
	print(test(a, b))


t = int(input())
for i in range(t):
	a = input()
	b = input()
	a_ = []
	b_ = []
	if len(a) > len(b):
		c = 0
		while len(b) + c != len(a):
			b_.append('0')
			c += 1
	elif len(a) < len(b):
		d = 0
		while len(a) + d != len(b):
			a_.append('0')
			d += 1
	for i in a:
		a_.append(i)
	for i in b:
		b_.append(i)
	pair = []
	for i in range(len(a_)):
		d = (a_[i], b_[i])
		pair.append(d)
	pair.reverse()
	pair_rev = pair
	if int(b) == 0:
		print(0)
	else:
		l = 0
		for i in range(len(pair_rev)):
			if pair_rev[i][0] == '1' and pair_rev[i][1] == '1':
				c = 1
				j = i + 1
				while j < len(pair_rev) and (pair_rev[j][0] == '1' and pair_rev[j][1] == '0' or (pair_rev[j][0] == '0' and pair_rev[j][1] == '1')):
					c += 1
					j += 1
				if l < c:
					l = c
		print(l + 1)


t = int(input())
while t > 0:
	t -= 1
	a = input().strip()
	b = input().strip()
	if len(b) == 1 and b[0] == '0':
		print(0)
		continue
	if len(a) > len(b):
		b = '0' * (len(a) - len(b)) + b
	else:
		a = '0' * (len(b) - len(a)) + a
	max_l = 0
	for i in range(len(a)):
		if b[i] == '1' and a[i] == '1':
			tmp = i - 1
			count = 1
			while tmp >= 0:
				if b[tmp] == '0' and a[tmp] == '1' or (b[tmp] == '1' and a[tmp] == '0'):
					count += 1
				else:
					break
				tmp -= 1
			max_l = max(max_l, count + 1)
	print(max(max_l, 1))


def make_eqlength(A, B):
	if len(A) < len(B):
		while len(A) < len(B):
			A = '0' + A
	else:
		while len(B) < len(A):
			B = '0' + B
	return (A, B)
t = int(input())
while t > 0:
	A = input()
	B = input()
	count = 0
	res = 1
	if int(B) == 0:
		print(0)
		t -= 1
		continue
	else:
		if len(A) != len(B):
			(A, B) = make_eqlength(A, B)
		flag = 0
		for (i, j) in zip(A[::-1], B[::-1]):
			if i == j:
				if i == '1':
					flag = 1
					count = 1
				elif i == '0' and j == '0':
					count = 0
					flag = 0
			elif flag == 1:
				count += 1
			c = count + 1
			res = max(res, c)
		print(res)
		t -= 1


for i in range(int(input())):
	C = '0'
	A = input()
	B = input()
	if len(A) < len(B):
		B = C + B
		C *= len(B) - len(A)
		A = C + A
	elif len(B) < len(A):
		A = C + A
		C *= len(A) - len(B)
		B = C + B
	else:
		A = C + A
		B = C + B
	a = 0
	dat = []
	b = 0
	if '1' not in B:
		print(0)
	elif '1' not in A:
		print(1)
	else:
		for i in range(1, len(A) + 1):
			if A[-i] != B[-i] and a != 0:
				b += 1
			elif A[-i] == B[-i] and a != 0:
				if A[-i] == '0':
					a = 0
				else:
					a = 1
				dat.append(b + 1)
				b = 1
			elif A[-i] == B[-i] and A[-i] == '1' and (a == 0):
				a = 1
				b = 1
		if len(dat) > 0:
			print(max(dat))
		else:
			print(1)


t = int(input())
while t > 0:
	t -= 1
	a = input().strip()
	b = input().strip()
	a = a[::-1]
	b = b[::-1]
	if b == '0':
		value = 0
	else:
		while len(a) < len(b):
			a += '0'
		while len(b) < len(a):
			b += '0'
		carry = 0
		cnt = 0
		value = 0
		for i in range(len(a)):
			cmp = carry + int(a[i]) + int(b[i])
			if cmp == 2:
				cnt += 1
				carry = 1
			elif cmp == 3:
				cnt = 1
				carry = 1
			else:
				cnt = 0
				carry = 0
			if cnt > value:
				value = cnt
		value += 1
	print(int(value))


T = int(input())
for i in range(T):
	A = input()
	B = input()
	if B == '0':
		print('0')
	else:
		if len(A) > len(B):
			B = B.zfill(len(A))
		else:
			A = A.zfill(len(B))
		ans = 1
		for i in range(len(A) - 1, -1, -1):
			if A[i] == '1' and B[i] == '1':
				temp = 2
				i -= 1
				while i >= 0:
					if A[i] != B[i]:
						i -= 1
						temp += 1
					if A[i] == B[i]:
						if A[i] == '1':
							i += 1
						break
				ans = max(temp, ans)
		print(ans)


t = int(input())
for _ in range(t):
	a = input()
	b = input()
	al = []
	suma = 0
	bl = []
	sumb = 0
	for i in range(len(a)):
		c = int(a[len(a) - i - 1])
		al.append(c)
		suma += c
	for i in range(len(b)):
		c = int(b[len(b) - i - 1])
		bl.append(c)
		sumb += c
	if sumb == 0:
		steps = 0
	elif suma == 0:
		steps = 1
	else:
		max = 1
		if len(al) > len(bl):
			for i in range(len(al) - len(bl)):
				bl.append(0)
		else:
			for i in range(len(bl) - len(al)):
				al.append(0)
		for i in range(len(al)):
			if al[i] == 1 and bl[i] == 1:
				count = 2
				i += 1
				while i < len(al):
					if al[i] ^ bl[i] == 1:
						count += 1
						i += 1
					else:
						break
				if count > max:
					max = count
		steps = max
	print(str(steps))


def addition(a, b, a1, b1):
	c = 0
	while b > 0:
		u = a ^ b
		v = a & b
		a = u
		b = v * 2
		c += 1
		if c > 100:
			sol(a1, b1)
			return
	print(c)

def binaryToDecimal(n):
	return int(n, 2)

def sol(a, b):
	a = list(a)
	b = list(b)
	if len(a) < l:
		for j in range(l - len(a)):
			a = ['0'] + a
	elif len(b) < l:
		for j in range(l - len(b)):
			b = ['0'] + b
	a.reverse()
	b.reverse()
	pa = []
	j = 0
	pa.append(0)
	while j < l:
		if a[j] == '1' and b[j] == '1':
			co = 1
			j += 1
			if j < l:
				while a[j] != b[j]:
					co += 1
					j += 1
					if j >= l:
						break
			pa.append(co)
		else:
			j += 1
	print(max(pa) + 1)
t = int(input())
for i in range(t):
	a = input()
	b = input()
	l = max(len(a), len(b))
	if b == '0':
		print(0)
	elif a == '0':
		print(1)
	else:
		a1 = binaryToDecimal(a)
		b1 = binaryToDecimal(b)
		addition(a1, b1, a, b)


for r in range(int(input())):
	x = input()
	y = input()
	m = 0
	na = len(x)
	nb = len(y)
	if na - 1 > 500 or nb - 1 > 500:
		if na > nb:
			y = (na - nb) * '0' + y
		elif nb > na:
			x = (nb - na) * '0' + x
		f = 0
		s = 0
		for i in range(len(x) - 1, -1, -1):
			if f == 0:
				if x[i] == '1' and y[i] == '1':
					s = 0
				elif x[i] == '0' and y[i] == '0':
					s = 0
					f = 1
				else:
					s += 1
					if s > m:
						m = s
			elif x[i] == '1' and y[i] == '1' and (f == 1):
				s = 0
				f = 0
			else:
				s = 0
		print(m + 2)
	else:
		x = int(x, 2)
		y = int(y, 2)
		s = 0
		while y > 0:
			u = x ^ y
			v = x & y
			x = u
			y = v * 2
			s += 1
		print(s)


t = int(input())
for _ in range(t):
	a = input()
	b = input()
	cnt = 0
	a = a[::-1]
	b = b[::-1]
	if b == '0':
		print('0\n')
	elif a == '0':
		print('1\n')
	else:
		while len(a) < len(b):
			a = a + '0'
		while len(b) < len(a):
			b = b + '0'
		a = a[::-1]
		b = b[::-1]
		(cnt, curr, maxi) = (1, -1, 0)
		for j in reversed(range(len(a))):
			if a[j] == b[j] == '1':
				curr = j
				cnt = 1
				maxi = max(maxi, cnt)
			elif curr > -1 and (a[j] == '0' and b[j] == '1' or (a[j] == '1' and b[j] == '0')):
				cnt += 1
				maxi = max(maxi, cnt)
			elif a[j] == b[j] == '0':
				curr = -1
		print(maxi + 1, '\n')


try:
	t = int(input())
	for _ in range(t):
		A = input()
		B = input()
		fcount = 0
		flag = 1
		DecimalA = int(A, 2)
		DecimalB = int(B, 2)
		if DecimalB == 0:
			print(0)
			continue
		if DecimalA == 0 and DecimalB != 0:
			print(1)
			continue
		var = abs(len(A) - len(B))
		if len(A) > len(B):
			B = '0' * var + B
		else:
			A = '0' * var + A
		i = len(A) - 1
		while i >= 0:
			count = 1
			if A[i] == B[i] and A[i] == '1':
				flag = 0
				j = i - 1
				while A[j] != B[j] and j >= 0:
					count += 1
					j -= 1
			if fcount < count:
				fcount = count
			i -= 1
		if flag == 0:
			print(fcount + 1)
		else:
			print(1)
except:
	pass


def solve(X, Y):
	if Y == '0':
		return 0
	n = max(len(X), len(Y))
	c = ''
	for i in range(abs(len(X) - len(Y))):
		c += '0'
	if len(X) < len(Y):
		X = c + X
	else:
		Y = c + Y
	ans = 1
	for i in range(n - 1, -1, -1):
		if X[i] == '1' and Y[i] == '1':
			cur = 2
			j = i - 1
			while j >= 0 and X[j] != Y[j]:
				j -= 1
				cur += 1
			ans = max(ans, cur)
	return ans
for _ in range(int(input())):
	X = input()
	Y = input()
	ans = solve(X, Y)
	print(ans)


t = int(input())
for _ in range(t):
	a = input()
	b = input()
	if '1' not in b:
		print(0)
	elif '1' not in a:
		print(1)
	else:
		n = max(len(a), len(b))
		a = a.zfill(n)
		b = b.zfill(n)
		count = 1
		for i in range(n):
			if a[i] == '1' and b[i] == '1':
				c = 2
				for j in range(i - 1, -1, -1):
					if a[j] != b[j]:
						c += 1
					else:
						break
				count = max(c, count)
		print(count)


def add(A, B):
	cnt = 0
	while B > 0:
		cnt += 1
		U = A ^ B
		B = (A & B) << 1
		A = U
	print(cnt)

def newfun(A, B):
	if len(A) > len(B):
		diff = len(A) - len(B)
		B = '0' * diff + B
	elif len(B) > len(A):
		diff = len(B) - len(A)
		A = '0' * diff + A
	l = len(A)
	A = A[::-1] + '0'
	B = B[::-1] + '0'
	ans = 0
	for i in range(l):
		temp = 1
		if A[i] == '1' and B[i] == '1':
			indx = 1
			while A[i + indx] != B[i + indx]:
				indx += 1
			temp += indx - 1
			if temp > ans:
				ans = temp
	print(ans + 1)
for t in range(int(input())):
	A = input()
	B = input()
	if B == '0':
		print('0')
	elif len(B) < 501 or len(A) < 501:
		A = int(A, 2)
		B = int(B, 2)
		add(A, B)
	else:
		newfun(A, B)


t = int(input())
ans = []
for _ in range(t):
	temp1 = input()
	temp2 = input()
	if len(temp1) <= 50000 and len(temp2) <= 50000:
		count = 0
		a = int(temp1, 2)
		b = int(temp2, 2)
		while b > 0:
			u = a ^ b
			v = a & b
			a = u
			b = v << 1
			count = count + 1
		ans.append(count)
	else:
		maximum = [0]
		c = list(temp1)
		d = list(temp2)
		c = c[::-1]
		d = d[::-1]
		if len(c) - len(d) > 0:
			temp = len(c) - len(d)
			for k in range(temp):
				d.append('0')
		if len(d) - len(c) > 0:
			temp = len(d) - len(c)
			for k in range(temp):
				c.append('0')
		flag = 0
		i = 0
		z = len(c)
		while i < z:
			count = 0
			if int(c[i]) == 1 and int(d[i]) == 1 and (i < z - 1):
				flag = 1
				i = i + 1
				if c[i] == d[i]:
					continue
				while 1:
					if c[i] != d[i]:
						i = i + 1
						count = count + 1
						if i >= z:
							break
					else:
						break
				maximum.append(count)
			i = i + 1
		if flag == 0:
			ans.append(1)
		else:
			ans.append(max(maximum) + 2)
for i in ans:
	print(i)


for _ in range(int(input())):
	a = input()
	b = input()
	x = int(a, 2)
	y = int(b, 2)
	if y == 0:
		print(0)
	elif x == 0 and y != 0:
		print(1)
	else:
		ans = 0
		count = 1
		f = 0
		if len(a) < len(b):
			d = len(b) - len(a)
			a = a.zfill(d + 1 + len(a))
			b = b.zfill(1 + len(b))
			n = len(a)
			for i in range(n - 1, -1, -1):
				if a[i] == '1' and b[i] == '1':
					if f == 1:
						ans = max(ans, count)
						count = 1
					else:
						f = 1
				if a[i] == '0' and b[i] == '0':
					if f == 1:
						ans = max(ans, count)
						count = 1
						f = 0
				if f == 1:
					if a[i] != b[i]:
						count += 1
						ans = max(ans, count)
		elif len(a) > len(b):
			d = len(a) - len(b)
			a = a.zfill(1 + len(a))
			b = b.zfill(d + 1 + len(b))
			n = len(a)
			for i in range(n - 1, -1, -1):
				if a[i] == '1' and b[i] == '1':
					if f == 1:
						ans = max(ans, count)
						count = 1
					else:
						f = 1
				if a[i] == '0' and b[i] == '0':
					if f == 1:
						ans = max(ans, count)
						count = 1
						f = 0
				if f == 1:
					if a[i] != b[i]:
						count += 1
						ans = max(ans, count)
		elif len(a) == len(b):
			a = a.zfill(1 + len(a))
			b = b.zfill(1 + len(b))
			n = len(a)
			for i in range(n - 1, -1, -1):
				if a[i] == '1' and b[i] == '1':
					if f == 1:
						ans = max(ans, count)
						count = 1
					else:
						f = 1
				if a[i] == '0' and b[i] == '0':
					if f == 1:
						ans = max(ans, count)
						count = 1
						f = 0
				if f == 1:
					if a[i] != b[i]:
						count += 1
						ans = max(ans, count)
		print(ans + 1)


for _ in range(int(input())):
	a = list(input())
	b = list(input())
	c = []
	(x, y) = (len(a), len(b))
	if x > y:
		c[:x - y + 1] = ['0'] * (x - y)
		c[x - y + 1:] = b[:]
		b = c
		z = x
	else:
		c[:y - x + 1] = ['0'] * (y - x)
		c[y - x + 1:] = a[:]
		a = c
		z = y
	t = 1
	r = 0
	if b == ['0'] * z:
		print(0)
	else:
		flag = 0
		for i in range(z - 1, -1, -1):
			if a[i] == b[i] == '1' and flag == 0:
				flag = 1
				t = t + 1
			elif a[i] == '1' and b[i] == '0' and (flag == 1) or (a[i] == '0' and b[i] == '1' and (flag == 1)):
				t = t + 1
			else:
				if t > r:
					r = t
				t = 1
				flag = 0
				if a[i] == b[i] == '1':
					flag = 1
					t = t + 1
		if t > r:
			r = t
		print(r)


t = int(input())
for _ in range(t):
	a = int(input(), 2)
	b = int(input(), 2)
	c = 0
	while b != 0:
		u = a ^ b
		v = a & b
		a = u
		b = 2 * v
		c += 1
	print(c)


def binaryToDecimal(binary):
	binary1 = binary
	(decimal, i, n) = (0, 0, 0)
	while binary != 0:
		dec = binary % 10
		decimal = decimal + dec * pow(2, i)
		binary = binary // 10
		i += 1
	return decimal

def add(a, b):
	count = 0
	u = 0
	v = 0
	while b > 0:
		u = a ^ b
		v = a & b
		a = u
		b = v * 2
		count = count + 1
	return count
t = int(input())
while t != 0:
	a = int(input())
	b = int(input())
	a = int(binaryToDecimal(a))
	b = int(binaryToDecimal(b))
	print(add(a, b))
	t = t - 1


def alt_add(A, B):
	C = int(A, 2)
	D = int(B, 2)
	if D == 0:
		return 0
	x = C & D
	y = C ^ D
	p = len(A)
	q = len(B)
	maxi = q
	if p > q:
		maxi = p
	x = bin(x)[2:].zfill(maxi)
	y = bin(y)[2:].zfill(maxi)
	maxi = 0
	max_till = 0
	for i in range(len(y)):
		if y[i] == '1' and x[i] == '0':
			maxi = maxi + 1
		elif y[i] == '0' and x[i] == '0':
			maxi = 0
		elif y[i] == '0' and x[i] == '1':
			max_till = max(max_till, maxi)
			maxi = 0
	if max_till == 0 and x.count('1') > 0:
		return 2
	elif max_till == 0 and x.count('1') == 0:
		return 1
	else:
		return max_till + 2
T = int(input())
for t in range(T):
	A = input().strip()
	B = input().strip()
	print(alt_add(A, B))


t = int(input())
for i in range(t):
	a = list(input())
	b = list(input())
	c = []
	(x, y) = (len(a), len(b))
	if x > y:
		c[:x - y + 1] = ['0'] * (x - y)
		c[x - y + 1:] = b[:]
		b = c
		z = x
	else:
		c[:y - x + 1] = ['0'] * (y - x)
		c[y - x + 1:] = a[:]
		a = c
		z = y
	k = 1
	r = 0
	if b == ['0'] * z:
		print(0)
	else:
		f = 0
		for j in range(z - 1, -1, -1):
			if a[j] == b[j] == '1' and f == 0:
				f = 1
				k += 1
			elif a[j] == '1' and b[j] == '0' and (f == 1) or (a[j] == '0' and b[j] == '1' and (f == 1)):
				k += 1
			else:
				if k > r:
					r = k
				k = 1
				f = 0
				if a[j] == b[j] == '1':
					f = 1
					k += 1
		if k > r:
			r = k
		print(r)


def add(a, b):
	count = 0
	u = 0
	v = 0
	while b > 0:
		u = a ^ b
		v = a & b
		a = u
		b = v * 2
		count = count + 1
	return count

def bruteforce(a, b):
	anum = int(a, 2)
	bnum = int(b, 2)
	print(add(anum, bnum))
t = int(input())
while t > 0:
	t = t - 1
	a = input()
	b = input()
	if int(b, 2) == 0:
		print('0')
		continue
	if int(a, 2) == 0:
		print('1')
		continue
	ashort = True
	if len(a) < len(b):
		ashort = True
	else:
		ashort = False
	if ashort == True:
		a = '0' * abs(len(a) - len(b)) + a
	else:
		b = '0' * abs(len(a) - len(b)) + b
	if len(a) < 90000:
		bruteforce(a, b)
		continue
	oneone = False
	maxi = 0
	ans = 0
	for i in range(len(a) - 1, -1, -1):
		if a[i] == '1' and b[i] == '1' or (a[i] == '0' and b[i] == '0'):
			oneone = True
			ans = max(ans, maxi)
			maxi = 0
		if oneone == True:
			if a[i] == '0' and b[i] == '1' or (a[i] == '1' and b[i] == '0'):
				maxi = maxi + 1
	print(ans + 2)


for _ in range(int(input())):
	a = input()
	b = input()
	(a, b) = (int(a, 2), int(b, 2))
	count = 0
	while b > 0:
		u = a ^ b
		v = a & b
		a = u
		b = v * 2
		count += 1
	print(count)


def main(debug=False):
	for _ in range(int(input())):
		a = input().strip()
		b = input().strip()
		a = a[::-1]
		b = b[::-1]
		while len(a) < len(b):
			a += '0'
		while len(b) < len(a):
			b += '0'
		if debug:
			print(a, b)
		(carry, ans, cur) = (0, 0, 0)
		for i in range(len(a)):
			carry = carry + int(a[i]) + int(b[i])
			if debug:
				print('For i=', i, 'a[i] b[i]', a[i], b[i])
			if carry == 2:
				cur += 1
			else:
				cur = carry // 2
			if debug:
				print('carry', carry)
				print('Curr', cur)
			carry = int(carry / 2)
			ans = max(ans, cur + 1)
			if debug:
				print('Ans', ans)
		if b.count('1') > 0:
			print(ans)
		else:
			print(0)
while True:
	try:
		main(debug=False)
	except (ValueError, EOFError) as e:
		break


tc = int(input())
for i in range(tc):
	a = input()
	b = input()
	l = 0
	l1 = len(a)
	l2 = len(b)
	if l1 > l2:
		l = l1
	else:
		l = l2
	a = a.zfill(l)
	b = b.zfill(l)
	temp = int(b, 2)
	if temp == 0:
		print(0)
	else:
		maxc = 0
		count = 0
		for i in range(l):
			if a[i] == '1' and b[i] == '1':
				count += 1
				maxc = max(count + 1, maxc)
				count = 0
			elif a[i] == '1' or b[i] == '1':
				count += 1
			else:
				count = 0
		if maxc == 0:
			print(1)
		else:
			print(maxc)


try:
	t = int(input())
	for _ in range(t):
		a = input()
		b = input()
		a = int(a, 2)
		b = int(b, 2)
		res = 0
		while b > 0:
			u = a ^ b
			v = a & b
			a = u
			b = v * 2
			res += 1
		print(res)
except:
	pass


for _ in range(int(input())):
	a = input()
	b = input()
	x = int(a, 2)
	y = int(b, 2)
	if y == 0:
		print(0)
	elif x == 0 and y != 0:
		print(1)
	else:
		ans = [0]
		count = 0
		f = 0
		if len(a) + len(b) > 100000:
			if len(a) < len(b):
				d = len(b) - len(a)
				a = a.zfill(d + 1 + len(a))
				b = b.zfill(1 + len(b))
				for i in range(len(a) - 1, -1, -1):
					if a[i] == '1' and b[i] == '1':
						if f == 1:
							ans.append(count)
							count = 0
							f = 0
						else:
							f = 1
					if a[i] == '0' and b[i] == '0':
						if f == 1:
							ans.append(count)
							count = 0
							f = 0
					if f == 1:
						count += 1
			if len(a) > len(b):
				d = len(a) - len(b)
				a = a.zfill(1 + len(a))
				b = b.zfill(d + 1 + len(b))
				for i in range(len(a) - 1, -1, -1):
					if a[i] == '1' and b[i] == '1':
						if f == 1:
							ans.append(count)
							count = 0
							f = 0
						else:
							f = 1
					if a[i] == '0' and b[i] == '0':
						if f == 1:
							ans.append(count)
							count = 0
							f = 0
					if f == 1:
						count += 1
			if len(a) == len(b):
				a = a.zfill(1 + len(a))
				b = b.zfill(1 + len(b))
				for i in range(len(a) - 1, -1, -1):
					if a[i] == '1' and b[i] == '1':
						if f == 1:
							ans.append(count)
							count = 0
							f = 0
						else:
							f = 1
					if a[i] == '0' and b[i] == '0':
						if f == 1:
							ans.append(count)
							count = 0
							f = 0
					if f == 1:
						count += 1
			print(max(ans) + 1)
		else:
			c = 0
			sum = x + y
			while y > 0:
				U = x ^ y
				x = U
				y = sum - x
				c = c + 1
			print(c)


t = int(input())
for j in range(t):
	a = input()
	b = input()
	n = len(a)
	n1 = len(b)
	A = int(a, 2)
	B = int(b, 2)
	c = 0
	max = 0
	if n - 1 > 500 or n1 - 1 > 500:
		s = '0' * abs(n - n1)
		if n > n1:
			b = s + b
		else:
			a = s + a
		a1 = a[::-1]
		b1 = b[::-1]
		flag = 0
		for i in range(len(a1)):
			if a1[i] == '0' and b1[i] == '0':
				flag = 0
				c = 0
			elif a1[i] == '1' and b1[i] == '1':
				flag = 1
				c = 0
			elif flag == 1:
				c = c + 1
				if c > max:
					max = c
		print(max + 2)
	else:
		while B > 0:
			U = A ^ B
			V = A & B
			A = U
			B = V * 2
			c = c + 1
		print(c)


def add(A, B):
	cnt = 0
	while B > 0:
		cnt += 1
		U = A ^ B
		V = A & B
		A = U
		B = V * 2
	return cnt
for _ in range(int(input().strip())):
	print(add(int(input().strip(), 2), int(input().strip(), 2)))


t = int(input())
while t != 0:
	a = input()
	b = input()
	t -= 1
	if int(b, 2) == 0:
		print(0)
	elif int(a, 2) == 0 or int(a, 2) & int(b, 2) == 0:
		print(1)
	else:
		a = '0' * (len(b) - len(a)) + a
		b = '0' * (len(a) - len(b)) + b
		count = 0
		c2 = 0
		flag = 0
		for i in range(len(b) - 1, -1, -1):
			ai = int(a[i])
			bi = int(b[i])
			if flag == 1:
				if ai ^ bi == 1:
					count += 1
				else:
					flag = 0
					count = 0
			if ai & bi == 1:
				flag = 1
			c2 = max(c2, count)
		print(c2 + 2)


t = input()
for _ in range(int(t)):
	a = input()
	b = input()
	carry = 0
	car_range = 0
	car_start = -1
	if int(b) == 0:
		print(0)
		continue
	c = a if len(a) > len(b) else b
	o = b if len(a) > len(b) else a
	c = c[::-1]
	o = o[::-1]
	for (i, x) in enumerate(c):
		y = 0
		if len(o) > i:
			y = o[i]
		if int(x) + int(y) == 1 and carry == 1:
			carry = 1
		elif int(x) + int(y) == 2 and carry == 0:
			carry = 1
		elif int(x) + int(y) == 2 and carry == 1:
			car_range = max(car_range, int(i) - int(car_start) + 1)
			car_start = i
			carry = 1
		else:
			carry = 0
		if carry > 0:
			if car_start == -1:
				car_start = i
		elif car_start != -1:
			car_range = max(car_range, int(i) - int(car_start) + 1)
			car_start = -1
	if carry > 0:
		car_range = max(car_range, int(len(c) - 1 + carry) - int(car_start) + 1)
	if car_range == 0:
		car_range = 1
	print(car_range)


t = int(input())
for i in range(t):
	a1 = input()
	b1 = input()
	val1 = 0
	val2 = 0
	u = 0
	v = 0

	def gen(m):
		val1 = int(a1, 2)
		val2 = int(b1, 2)
		c = 0
		while m > 0:
			c += 1
			u = val1 ^ m
			v = val1 & m
			val1 = u
			m = 2 * v
		yield c
	val2 = int(b1, 2)
	g = gen(val2)
	for i in g:
		print(i)


for i in range(int(input())):
	a = input()
	a = int(a, 2)
	b = input()
	b = int(b, 2)
	num = 0
	while b > 0:
		u = a ^ b
		v = a & b
		a = u
		b = v * 2
		num += 1
	print(num)


import math
t = int(input())
for _ in range(0, t):
	a = input()
	b = input()
	if len(a) < len(b):
		a = '0' * abs(len(a) - len(b)) + a
	elif len(b) < len(a):
		b = '0' * abs(len(a) - len(b)) + b
	a = '0' + a
	b = '0' + b
	if int(b, 2) == 0:
		print(0)
		continue
	i = len(a) - 1
	j = i
	maxi = -1
	ls = [1]
	cnt = 0
	while i >= 0:
		if a[i] == '1' and b[i] == '1':
			j = i - 1
			cnt = 1
			while a[j] == '1' and b[j] == '0' or (a[j] == '0' and b[j] == '1' and (j >= 0)):
				cnt += 1
				j -= 1
			ls.append(cnt + 1)
			i = j
		else:
			i -= 1
	print(max(ls))


for _ in range(int(input())):
	a = input()
	b = input()
	m = len(a)
	n = len(b)
	if m > n:
		for i in range(m - n):
			b = '0' + b
	elif n > m:
		for i in range(n - m):
			a = '0' + a
		m = n
	l = [-1 for i in range(m)]
	for i in range(m - 1, -1, -1):
		if a[i] == '1' and b[i] == '1':
			l[i] = 0
	j = -1
	for i in range(m - 1, -1, -1):
		if a[i] == '1' and b[i] == '1':
			if j != -1:
				l[j] = l[j] + 1
			j = i
		elif a[i] == '0':
			if b[i] == '0':
				if j != -1:
					l[j] = l[j] + 1
					j = -1
			elif j != -1:
				l[j] = l[j] + 1
		elif b[i] == '0':
			if j != -1:
				l[j] = l[j] + 1
	if a[0] == '1' and b[0] == '1':
		l[j] = l[j] + 1
	elif j != -1:
		l[j] = l[j] + 1
	if int(b) == 0:
		print(0)
	elif max(l) == -1:
		print(1)
	else:
		print(max(l) + 1)


from sys import stdin, stdout
for i in range(int(stdin.readline())):
	stra = int(stdin.readline(), 2)
	strb = int(stdin.readline(), 2)
	count = 0
	while strb != 0:
		(stra, strb) = [stra ^ strb, (stra & strb) * 2]
		count += 1
	print(count)


t = int(input())
while t > 0:
	a = input()
	b = input()
	l1 = len(a)
	l2 = len(b)
	l = 0
	if l1 > l2:
		l += l1
	else:
		l += l2
	a = a.zfill(l)
	b = b.zfill(l)
	cnt = 0
	k = 0
	for i in range(0, l):
		if a[i] == '1' and b[i] == '1':
			cnt += 1
			k = max(cnt, k)
			cnt = 0
		elif a[i] == '1' or b[i] == '1':
			cnt += 1
		else:
			cnt = 0
	b = int(b, 2)
	if b == 0:
		print(0)
	else:
		print(k + 1)
	t -= 1


for i in range(0, int(input())):
	m = input()
	n = input()
	if n == '0':
		print(0)
	elif n != '0':
		if len(m) > len(n):
			diff = len(m) - len(n)
			for j in range(diff):
				n = '0' + n
		elif len(n) > len(m):
			diff = len(n) - len(m)
			for j in range(diff):
				m = '0' + m
		m = '0' + m
		n = '0' + n
		lenm = len(m)
		L = []
		L.append(0)
		m = m[::-1]
		n = n[::-1]
		for k in range(lenm - 1):
			A = 1
			if m[k] == '1' and n[k] == '1':
				chk = 1
				brk = 1
				while brk == 1:
					if m[chk + k] == '1' and n[chk + k] == '0':
						A += 1
					elif m[chk + k] == '0' and n[chk + k] == '1':
						A += 1
					else:
						brk = 0
					chk += 1
				L.append(A)
		print(max(L) + 1)


T = int(input())
for k in range(T):
	a = input()
	b = input()
	if b == '0':
		print('0')
	elif a == '0':
		print('1')
	else:
		if len(a) > len(b):
			b = '0' * (len(a) - len(b)) + b
		else:
			a = '0' * (len(b) - len(a)) + a
		mx = 1
		flag = -1
		count = 0
		for i in range(len(a) - 1, -1, -1):
			if flag == 0:
				if a[i] == '1' and b[i] == '0' or (b[i] == '1' and a[i] == '0'):
					count = 1 + count
				else:
					flag = -1
					count = 0
			if a[i] == b[i] and a[i] == '1':
				flag = 0
				count = 2
			if count > mx:
				mx = count
		print(mx)


def ones(n):
	c = 0
	while n:
		n = n & n - 1
		c += 1
	if c == 1:
		return True
	return False

def cc(a, b):
	a = bin(a)[2:]
	b = bin(b)[2:]
	sa = len(a)
	sb = len(b)
	ind = -1
	qq = abs(sa - sb)
	y = 0
	if qq == 0:
		ind = 0
		qq += 1
		y += 1
	if sa - sb > 0:
		for i in range(qq, sa):
			if a[i] == '1' and b[y] == '1':
				ind = i
				break
			y += 1
	else:
		for i in range(qq, sb):
			if b[i] == '1' and a[y] == '1':
				ind = i
				break
			y += 1
	return ind
for _ in range(int(input())):
	a = int(input(), 2)
	b = int(input(), 2)
	if b == 0:
		print('0')
		continue
	if a == 0:
		print('1')
		continue
	c = 0
	f = 0
	while True:
		c += 1
		u = a ^ b
		v = a & b
		if v == 0:
			break
		a = u
		b = v << 1
		if ones(b):
			f = 1
			break
	if f == 1:
		k = 0
		z = a | b
		z = bin(z)[2:]
		index = cc(a, b)
		for i in range(index, -1, -1):
			if z[i] == '1':
				k += 1
			else:
				break
		c += max(k + 1, 1)
	print(c)


TESTCASES = int(input())
for i in range(0, TESTCASES):
	A = input().strip()[::-1]
	B = input().strip()[::-1]
	if '1' not in B:
		print('0')
		continue
	while len(A) < len(B):
		A += '0'
	while len(B) < len(A):
		B += '0'
	LL = 1
	CC = False
	JJ = 0
	for i in range(0, len(A)):
		ACC = A[i] == '1'
		BCC = B[i] == '1'
		if ACC and BCC:
			CC = True
			JJ = 2
			LL = max(LL, JJ)
		elif ACC ^ BCC and CC:
			JJ += 1
			LL = max(LL, JJ)
		else:
			CC = False
	print(LL)


for _ in range(int(input())):
	a = input()
	b = input()
	bog = b
	an = len(a)
	bn = len(b)
	ans = -1
	p = 0
	if an > bn:
		b = b.zfill(an - bn + bn)
		p = an
	elif bn > an:
		a = a.zfill(bn - an + an)
		p = bn
	else:
		p = an
	al = list(map(int, a))
	bl = list(map(int, b))
	res = [7]
	if bog == '0':
		ans = 0
		print(ans)
		continue
	else:
		for i in range(p):
			if al[i] == 0 and bl[i] == 0:
				res.append(7)
			elif al[i] == 0 and bl[i] == 1 or (al[i] == 1 and bl[i] == 0):
				res.append(8)
			elif al[i] == 1 and bl[i] == 1:
				res.append(9)
	if res.count(9) == 0:
		ans = 1
	else:
		po = 0
		ma = 1
		flag = 1
		for i in range(p + 1):
			if res[i] == 7:
				po = i
			elif res[i] == 9:
				if ma < abs(i - po + 1):
					ma = abs(i - po + 1)
				po = i
		ans = ma
	print(ans)


t = int(input())
while t != 0:
	A = input()
	B = input()
	C = int(A, 2)
	D = int(B, 2)
	x = C & D
	y = C ^ D
	p = len(A)
	q = len(B)
	maxi = 0
	if p > q:
		maxi = p
	else:
		maxi = q
	x = bin(x)[2:].zfill(maxi)
	y = bin(y)[2:].zfill(maxi)
	maxi = 0
	max_till = 0
	if D == 0:
		print('0')
	else:
		for i in range(len(y)):
			if y[i] == '1' and x[i] == '0':
				maxi = maxi + 1
				continue
			elif y[i] == '0' and x[i] == '0':
				maxi = 0
			elif y[i] == '0' and x[i] == '1':
				max_till = max(max_till, maxi)
				maxi = 0
		if max_till == 0 and x.count('1') > 0:
			print('2')
		elif max_till == 0 and x.count('1') == 0:
			print('1')
		else:
			print(max_till + 2)
	t -= 1


T = int(input())
while T:
	A = input()
	B = input()
	if B == '0':
		print(0)
	else:
		if len(A) < len(B):
			add = ''
			for i in range(len(B) - len(A)):
				add += '0'
			A = add + A
		elif len(B) < len(A):
			add = ''
			for i in range(len(A) - len(B)):
				add += '0'
			B = add + B
		maxval = 0
		curval = 0
		for i in range(len(A) - 1, -1, -1):
			if A[i] == '0' and B[i] == '0':
				curval = 0
			elif A[i] == '1' and B[i] == '1':
				curval = 1
			elif curval > 0:
				curval += 1
			maxval = max(curval, maxval)
		print(maxval + 1)
	T -= 1


t = int(input())
for i in range(t):
	A1 = int(input(), 2)
	B1 = int(input(), 2)
	outer = 0
	while B1 > 0:
		outer += 1
		u = A1 ^ B1
		B1 = A1 + B1 - u
		A1 = u
	print(outer)


import math
import sys
from collections import Counter

def add(x, y):
	cnt = 0
	while y > 0:
		u = x ^ y
		v = x & y
		x = u
		y = v * 2
		cnt += 1
	return cnt
T = int(input())
for _ in range(0, T):
	a = input()
	b = input()
	print(add(int(a, 2), int(b, 2)))


def loji_hogya(a, b):
	count = 0
	while b > 0:
		u = a ^ b
		v = a & b
		a = u
		b = v * 2
		count = count + 1
	return count
n = int(input())
while n != 0:
	a = input()
	b = input()
	a = int(a, 2)
	b = int(b, 2)
	print(loji_hogya(a, b))
	n = n - 1


T = int(input())
for i in range(T):
	a = input()
	b = input()
	al = len(a)
	bl = len(b)
	if al > 450 and bl > 450:
		x = max(al, bl)
		if al > bl:
			for i in range(al - bl):
				b = '0' + b[:]
		elif al < bl:
			for i in range(bl - al):
				a = '0' + a[:]
		else:
			pass
		res = 1
		req = 1
		for j in range(x - 1, -1, -1):
			t = 1
			if b[j] == '1':
				req = 0
			if a[j] == '1' and b[j] == '1':
				t = t + 1
				for k in range(j - 1, -1, -1):
					if a[k] == '0' and b[k] == '1' or (a[k] == '1' and b[k] == '0'):
						t = t + 1
					else:
						break
				j = k + 1
				if t > res:
					res = t
		if req == 1:
			print('0')
		else:
			print(res)
	else:
		A = int(a, 2)
		B = int(b, 2)
		count = 0
		if B == 0:
			print('0')
		elif A == 0:
			print('1')
		else:
			while B > 0:
				count = count + 1
				temp = A & B
				A = A ^ B
				B = temp * 2
			print(count)


t = int(input())
for i in range(t):
	A = input()
	B = input()
	arr = []
	lenA = len(A)
	lenB = len(B)
	if lenA < lenB:
		A = (lenB - lenA) * '0' + A
	else:
		B = (lenA - lenB) * '0' + B
	for j in range(max(lenA, lenB)):
		arr.append(int(A[j]) + int(B[j]))
	j = len(arr) - 1
	count_max = 0
	count = 0
	while j >= 0:
		if arr[j] == 2:
			if count > count_max:
				count_max = count
			count = 1
		elif arr[j] == 1 and count != 0:
			count += 1
		elif arr[j] == 0:
			if count > count_max:
				count_max = count
			count = 0
		j -= 1
	if count > count_max:
		count_max = count
	if int(B) == 0:
		print(0)
	else:
		print(count_max + 1)