You are given two binary strings $x$ and $y$, which are binary representations of some two integers (let's denote these integers as $f(x)$ and $f(y)$). You can choose any integer $k \ge 0$, calculate the expression $s_k = f(x) + f(y) \cdot 2^k$ and write the binary representation of $s_k$ in reverse order (let's denote it as $rev_k$). For example, let $x = 1010$ and $y = 11$; you've chosen $k = 1$ and, since $2^1 = 10_2$, so $s_k = 1010_2 + 11_2 \cdot 10_2 = 10000_2$ and $rev_k = 00001$.

For given $x$ and $y$, you need to choose such $k$ that $rev_k$ is lexicographically minimal (read notes if you don't know what does "lexicographically" means).

It's guaranteed that, with given constraints, $k$ exists and is finite.


-----Input-----

The first line contains a single integer $T$ ($1 \le T \le 100$) — the number of queries.

Next $2T$ lines contain a description of queries: two lines per query. The first line contains one binary string $x$, consisting of no more than $10^5$ characters. Each character is either 0 or 1.

The second line contains one binary string $y$, consisting of no more than $10^5$ characters. Each character is either 0 or 1.

It's guaranteed, that $1 \le f(y) \le f(x)$ (where $f(x)$ is the integer represented by $x$, and $f(y)$ is the integer represented by $y$), both representations don't have any leading zeroes, the total length of $x$ over all queries doesn't exceed $10^5$, and the total length of $y$ over all queries doesn't exceed $10^5$.


-----Output-----

Print $T$ integers (one per query). For each query print such $k$ that $rev_k$ is lexicographically minimal.


-----Example-----
Input
4
1010
11
10001
110
1
1
1010101010101
11110000

Output
1
3
0
0



-----Note-----

The first query was described in the legend.

In the second query, it's optimal to choose $k = 3$. The $2^3 = 1000_2$ so $s_3 = 10001_2 + 110_2 \cdot 1000_2 = 10001 + 110000 = 1000001$ and $rev_3 = 1000001$. For example, if $k = 0$, then $s_0 = 10111$ and $rev_0 = 11101$, but $rev_3 = 1000001$ is lexicographically smaller than $rev_0 = 11101$.

In the third query $s_0 = 10$ and $rev_0 = 01$. For example, $s_2 = 101$ and $rev_2 = 101$. And $01$ is lexicographically smaller than $101$.

The quote from Wikipedia: "To determine which of two strings of characters comes when arranging in lexicographical order, their first letters are compared. If they differ, then the string whose first letter comes earlier in the alphabet comes before the other string. If the first letters are the same, then the second letters are compared, and so on. If a position is reached where one string has no more letters to compare while the other does, then the first (shorter) string is deemed to come first in alphabetical order."

Difficulty: interview

Starter code:

Solutions:
T = int(input())

for _ in range(T):
	x = input()[::-1]
	y = input()[::-1]

	start = y.index("1")

	offset = x[start:].index("1")

	print(offset)

n=int(input())
for _ in range(n):
	a=input()[::-1]
	b=input()[::-1]
	x=b.find("1")
	print(a.find("1", x)-x)

res = []
for TT in range(1, int(input()) + 1):
    a, b = input()[::-1], input()[::-1]
    i = b.index('1')
    j = a[i:].index('1')
    res.append(j)
print(*res, sep='\n')

t = int(input())

for _ in range(t):
    s1 = input()[::-1]
    s2 = input()[::-1]

    pos2 = -1
    for i, c in enumerate(s2):
        if c == '1':
            pos2 = i
            break

    if pos2 == -1:
        print(0)
        continue
    
    ok = False
    for j in range(pos2, len(s1)):
        if s1[j] == '1':
            print(j - pos2)
            ok = True
            break

    if not ok:
        print(0)

for _ in range(int(input())):
    x = input()
    y = input()
    sh = len(y) - y.rfind("1")
    #ans = 0
    cnt = 0
    for i in range(len(x) - sh, -1, -1):
        if x[i] == "1":
            #ans = cnt 
            break
        else:
            cnt += 1
    print(cnt)


t = int(input())
for _ in range(t):
    x = input()
    y = input()
    r = y.rfind('1')
    if r < 0:
        print( 0 )
    else:
        l = len(x) - len(y) + r
        print( l - x[:l+1].rfind('1') )


n = int(input())
for _ in range(n):
    a = input()
    b = input()
    a = a[::-1]
    b = b[::-1]
    indb = 0
    for i in range(len(b)):
        if b[i] == '1':
            indb = i
            break
    inda = 0
    for i in range(indb,len(a)):
        if a[i] == '1':
            inda = i
            break
    
    print(max(inda-indb,0))

t=int(input())
for nt in range(t):
	x=input()
	y=input()
	count=0
	for i in range(len(y)-1,-1,-1):
		if y[i]=="0":
			count+=1
		else:
			break
	k=0
	for i in range(len(x)-1-count,-1,-1):
		if x[i]=="1":
			break
		else:
			k+=1
	print (k)




t = int(input())
for _ in range(t):
    x = input()
    y = input()
    lst = len(y) - y.rfind('1')
    out = False
    for i in range(lst, len(x) + 1):
        if x[-i] == '1':
            print(i - lst)
            out = True
            break
    if out:
        continue



import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
	x = input().strip()
	y = input().strip()
	m = len(x)
	n = len(y)
	c = 1
	while True:
		if y[n - c] == '1':
			break
		else:
			c += 1		
	j = m - c
	k = 0
	while (j >= 0):
		if x[j] == '1':
			print(k)
			break
		else:
			j -= 1
			k += 1


import sys
input = sys.stdin.readline

T = int(input())

for t in range(T):
    x = input()
    y = input()
    pos_y = y.rfind('1')
    d = len(y) - pos_y - 1
    if d != 0:
        pos_x = x[:-d].rfind('1')
    else:
        pos_x = x.rfind('1')
    pos_x = -len(x) + pos_x
    pos_y = -len(y) + pos_y
    k = pos_y - pos_x
    print(k)


import sys
input = sys.stdin.readline

T = int(input())
x = []
y = []
for i in range(2*T):
    if i%2==0:
        x.append(input())
    else:
        y.append(input())

for i in range(T):
    n = len(y[i])
    for j in range(n):
        if y[i][n-j-1]=='1':
            break
    n = len(x[i])
    for k in range(j,n):
        if x[i][n-k-1]=='1':
            break
    print(k-j)       


import sys

T = int(sys.stdin.readline().strip())

for i in range (0, T):
    x = sys.stdin.readline().strip()
    y = sys.stdin.readline().strip()
    w = 0
    while y[-w-1] == '0':
        w = w + 1
    v = w
    while x[-v-1] == '0':
        v = v + 1
    print(v - w)


from sys import stdin
input=stdin.readline
for i in range(int(input())):
    x=input()[::-1]
    y=input()[::-1]
    k=0
    for i in range(len(y)):
        if y[i]=='1':
            break
    while i<len(x):
        if x[i]=='1':
            break
        i+=1
        k+=1
    print(k)


t = int(input())
for _ in range(t):
	x = input()
	y = input()
	i = 1
	while y[-i] == "0":
		i += 1
	j = 0
	while x[-i-j] == "0":
		j += 1
	print(j)

q = int(input())

for _ in range(q):
    x = list(input())
    y = list(input())

    i = 0

    while y[-i-1] == '0':
        i += 1

    j = i

    while x[-i-1] == '0':
        i+= 1

    print(i-j)


T = int(input())
for _ in range(T):
    x = input()
    y = input()
    x = x[::-1]
    y = y[::-1]
    p = -1
    for i in range(len(y)):
        if y[i] == '1':
            p = i 
            break
    q = -1
    for i in range(len(x)):
        if x[i] == '1' and i >= p:
            q = i
            break
    ans = q - p
    print(ans)


t = int(input())
for tt in range(t):
    x = input()
    y = input()
    b = list(reversed(y)).index('1')
    a = list(reversed(x))[b:].index('1')
    print(a)


for t in range(int(input())):
    s = input()
    c = input()
    ls = len(s)
    lc = len(c)
    for i in range(lc-1, -1, -1):
        if c[i] == '1':
            break
    ans = 0
    for j in range(ls-(lc-i), -1, -1):
        if s[j] == '1':
            break
        ans += 1
    print(ans)


t = int(input())
for i in range(t):
    a = input()[::-1]
    b = input()[::-1]
    j = 0
    while b[j] == '0':
        j += 1
    res = 0
    while a[j] == '0':
        j += 1
        res += 1
    print(res)

t = int(input())
for i in range(t):
    x = input()
    y = input()
    num = y.rfind("1")
    if num != -1:
        if x.rfind("1") == -1:
            print(0)
        else:
            ans = 0
            for i in range(len(x) - len(y) + num,-1,-1):
                if x[i] == "1":
                    ans = len(x) - len(y) + num - i
                    break
            print(ans)
    else:
        print(0)
        


t=int(input())
for l in range(t):
	a=str(input())
	b=str(input())
	a=a[::-1]
	b=b[::-1]
	s1=-1
	for i in range(len(b)):
		if(b[i]=='1'):
			s1=i
			break
	if(s1==-1):
		print(0)
	else:
		ans=0
		for j in range(len(a)):
			if(a[j]=='1' and j>=i):
				ans=j-i
				break
		print(ans)


def mp():
    return map(int, input().split())

t = int(input())

for tt in range(t):
    x = input()
    y = input()
    
    x = x[::-1]
    y = y[::-1]
    
    x_i = x.find('1')
    y_i = y.find('1')
    
    if x_i >= y_i:
        print(x_i - y_i)
    else:
        for i in range(y_i, len(x)):
            if x[i] == '1':
                print(i - y_i)
                break

for _ in range(int(input())):
    s, t = input(), input()
    w = s[:t.rfind('1') + len(s) - len(t) + 1]
    print(len(w) - w.rfind('1') - 1)

t = int(input())
for _ in range(t) :
    x = input()
    y = input()
    ind = 0
    ind2 = 0
    for k in range(len(y)) :
        i = len(y)-1-k
        if y[i] == "1" :
            ind2 = k
            break
    for k in range(ind2, len(x)) :
        i = len(x)-1-k
        if x[i] == "1" :
            ind = k
            break
    print(max(0, ind-ind2))