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: interview

Starter code:

Solutions:
def add(A, B):
 cnt = 0
 while B > 0:
  U = A ^ B
  B = (A & B) * 2
  A = U
  cnt += 1
 return cnt

for _ in range(int(input())):
 print(add(int(input(),2), int(input(), 2)))

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)))

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)))

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

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)

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)


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)


# cook your dish here
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)


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)))


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)))

# cook your dish here
t=int(input())
for _ in range(t):
 a=int(input(),2)
 b=int(input(),2)
 c=0
 while b>0:
  x=a^b 
  v=a&b 
  a=x 
  b=v*2 
  c+=1 
 print(c)

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)
 


# cook your dish here
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 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


# cook your dish here
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(a)
 #print(b)
 print(add(a,b))
 t=t-1


# cook your dish here
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(a)
 #print(b)
 print(add(a,b))
 t=t-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
  b = 2*(a&b)
  a = u
  #b = 2*v
  i+=1

 print(i)

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)

# cook your dish here
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)

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)