Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

Chef has two integers $A$ and $B$. He can perform the following operation on $A$ an arbitrary number of times (including zero):
write $A$ as a binary number with an arbitrary number of leading zeroes (possibly without any)
shuffle the binary digits of $A$ in an arbitrary way, obtaining a number $s$
replace $A$ by $s+1$

Chef is wondering about the minimum number of operations he has to perform on $A$ in order to obtain $B$. Compute this number or determine that it is impossible.

------  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 two space-separated integers $A$ and $B$. 

------  Output ------
For each test case, print a single line containing one integer — the minimum number of operations or $-1$ if it is impossible to obtain $B$ from $A$.

------  Constraints  ------
$1 ≤ T ≤ 10^{5}$
$0 ≤ A, B ≤ 10^{18}$

------  Subtasks ------
Subtask #1 (20 points): $A, B ≤ 2^{7}$

Subtask #2 (80 points): original constraints

----- Sample Input 1 ------ 
2
2 4
1 5
----- Sample Output 1 ------ 
2
1
----- explanation 1 ------ 
Example case 1: One optimal solution is to not shuffle anything, so Chef just adds $1$ twice. 

Example case 2: We can obtain $5$ from $1$ in one operation.

Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Graph algorithms

Graph traversal

Shortest paths

Mathematics
Skill types: Bit manipulation

Starter code:

Solutions:
for z in range(int(input())):
	(a, b) = (int(x) for x in input().split())
	if a == b:
		print('0')
	elif b == 1 and a == 0:
		print('1')
	elif b == 1 or b == 0:
		print('-1')
	else:
		c1 = b - 1
		bib = bin(c1)[2:]
		bia = bin(a)[2:]
		a1 = bia.count('1')
		b1 = bib.count('1')
		if a1 == b1:
			print('1')
		elif a1 < b1:
			print(b1 - a1 + 1)
		else:
			print('2')


def setBits(n):
	cnt = 0
	while n > 0:
		rsbm = n & -n
		n -= rsbm
		cnt += 1
	return cnt
t = int(input())
for i in range(t):
	(a, b) = list(map(int, input().split()))
	if a == b:
		print(0)
		continue
	elif b == 0:
		print(-1)
		continue
	elif b == 1:
		if a == 0:
			print(1)
			continue
		else:
			print(-1)
			continue
	na = setBits(a)
	nb = setBits(b - 1)
	if na > nb:
		print(2)
	else:
		print(nb - na + 1)


def snek(n):
	c = 0
	while n > 0:
		r = n & -n
		n -= r
		c += 1
	return c
t = int(input())
for i in range(t):
	(a, b) = list(map(int, input().split()))
	if a == b:
		print(0)
		continue
	elif b == 0:
		print(-1)
		continue
	elif b == 1:
		if a == 0:
			print(1)
			continue
		else:
			print(-1)
			continue
	n1 = snek(a)
	n2 = snek(b - 1)
	if n1 > n2:
		print(2)
	else:
		print(n2 - n1 + 1)


for t in range(int(input())):
	(A, B) = map(int, input().split(' '))
	(countA, countB) = (str(bin(A)).count('1'), str(bin(B - 1)).count('1'))
	if A == B:
		print('0')
	elif A != 0 and (B == 0 or B == 1):
		print('-1')
		pass
	elif countA > countB:
		print('2')
		pass
	else:
		print(countB - countA + 1)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	c1 = bin(a).count('1')
	c2 = bin(b - 1).count('1')
	ans = c2 - c1 + 1
	if a == b:
		print(0)
	elif a == 0 and b == 1:
		print(1)
	elif b == 0 or b == 1:
		print(-1)
	elif ans <= 0:
		print(2)
	else:
		print(ans)


for T in range(int(input())):
	(A, B) = input().split()
	A = bin(int(A))[2:]
	B = bin(int(B))[2:]
	A1 = A.count('1')
	B1 = B.count('1')
	if A == B:
		print(0)
		continue
	if B == '1' or B == '0':
		print([-1, 1][B == '1' and A == '0'])
		continue
	B1 = B1 + (len(B) - B.rindex('1') - 1)
	if B1 - A1 > 0:
		print(B1 - A1)
	else:
		print(2)


from math import *
T = int(input())
for i in range(T):
	(A, B) = list(map(int, input().split(' ')))
	oa = 0
	ob = 0
	zb = 0
	y = 0
	r = True
	para = True
	if A == B:
		print(0)
		r = False
	elif B == 1:
		if A == 0:
			print(1)
			r = False
		else:
			print(-1)
			r = False
	elif B == 0:
		print(-1)
		r = False
	if r == True:
		io = 1
		while A > 0:
			d = A % 2
			oa = oa + d
			A = A // 2
		if B == 0:
			zb = 1
		else:
			while B > 0:
				y = B % 2
				ob = ob + y
				if para:
					if y:
						para = False
					else:
						zb += 1
				B = B // 2
		fina = ob - oa
		fina1 = fina + zb
		if fina1 <= 0:
			print(2)
		else:
			print(fina1)


def count_ones(a):
	return bin(a)[2:].count('1')

def count_opts(a, b):
	if a == b:
		return 0
	elif b == 0:
		return -1
	elif b == 1:
		if a == 0:
			return 1
		else:
			return -1
	opts = count_ones(b - 1) - count_ones(a) + 1
	if opts > 0:
		return opts
	else:
		return 2
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	print(count_opts(a, b))


def bcnt(x):
	res = 0
	for i in range(0, 64):
		if x >> i & 1 == 1:
			res = res + 1
	return res
for _ in range(0, int(input())):
	(a, b) = map(int, input().split())
	if a == b:
		print(0)
	elif b == 0 and a > 0 or (b == 1 and a > 1):
		print(-1)
	elif bcnt(a) > bcnt(b - 1):
		print(2)
	else:
		print(bcnt(b - 1) - bcnt(a) + 1)


for z in range(int(input())):
	(a, b) = (int(x) for x in input().split())
	if a == b:
		print('0')
	elif b == 1 and a == 0:
		print('1')
	elif b == 1 or b == 0:
		print('-1')
	else:
		c1 = b - 1
		q = bin(c1)[2:]
		p = bin(a)[2:]
		s = p.count('1')
		t = q.count('1')
		if s == t:
			print('1')
		elif s < t:
			print(t - s + 1)
		else:
			print('2')


for _ in range(int(input())):
	(a, b) = [int(x) for x in input().split()]
	if a == b:
		print(0)
	elif a == 0 and b == 1:
		print(1)
	elif b <= 1:
		print(-1)
	else:
		b -= 1
		(x, y) = (bin(a)[2:], bin(b)[2:])
		(c1, c2) = (x.count('1'), y.count('1'))
		if c1 == c2:
			print(1)
		elif c1 < c2:
			print(c2 - c1 + 1)
		else:
			print(2)


def num(A):
	cnt = 0
	while A > 0:
		if A % 2 == 1:
			cnt += 1
		A = A // 2
	return cnt
t = int(input())
for kk in range(t):
	(A, B) = list(map(int, input().split()))
	if A == B:
		print(0)
	elif B == 0 and A > 0:
		print(-1)
	elif B == 1 and A > 1:
		print(-1)
	elif B == 1 and A == 0:
		print(1)
	else:
		B -= 1
		if num(A) > num(B):
			print(2)
		else:
			print(num(B) - num(A) + 1)


n = int(input())
for i in range(0, n):
	arr = [int(x) for x in input().split(' ')]
	if arr[0] == arr[1]:
		print(0)
		continue
	if arr[1] == 0 or (arr[1] == 1 and arr[0] > 0):
		print(-1)
		continue
	nb = bin(arr[1] - 1).count('1')
	na = bin(arr[0]).count('1')
	if nb < na:
		print(2)
		continue
	if nb == na:
		print(1)
		continue
	if nb > na:
		print(nb - na + 1)


t = int(input())
for i in range(t):
	(a, b) = [int(x) for x in input().split()]
	if a == b:
		print(0)
	elif b == 0:
		print(-1)
	elif b == 1:
		if a == 0:
			print(1)
		else:
			print(-1)
	else:
		aa = bin(a)
		bb = bin(b - 1)
		oa = aa.count('1')
		ob = bb.count('1')
		if oa > ob:
			print(2)
		else:
			print(ob - oa + 1)


def set_bits(n):
	return bin(n).count('1')
t = int(input())
for test in range(t):
	(a, b) = map(int, input().split())
	if a == b:
		ans = 0
	elif b == 0 or (a > 0 and b == 1):
		ans = -1
	else:
		set_bits_a = set_bits(a)
		set_bits_b_less_1 = set_bits(b - 1)
		if set_bits_a <= set_bits_b_less_1:
			ans = set_bits_b_less_1 - set_bits_a + 1
		else:
			ans = 2
	print(ans)


T = int(input())
for i in range(T):
	(A, B) = map(int, input().split())
	if A == B:
		print(0)
	elif B == 0:
		print(-1)
	elif B == 1:
		if A == 0:
			print(1)
		else:
			print(-1)
	else:
		a1 = bin(A)
		a = a1.count('1')
		b1 = bin(B - 1)
		b = b1.count('1')
		if a == b:
			print(1)
		elif a < b:
			print(b - a + 1)
		elif a > b:
			print(2)


def countone(num):
	count = 0
	while num > 0:
		num = num & num - 1
		count += 1
	return count
T = int(input())
for t in range(T):
	(A, B) = map(int, input().split())
	a = '{0:b}'.format(A)
	b = '{0:b}'.format(B)
	x = len(a)
	y = len(b)
	anum1 = countone(A)
	bnum1 = countone(B)
	count = 0
	if B == 0 and A > 0:
		print(-1)
	elif B == 1 and A > 1:
		print(-1)
	elif A == B:
		print(0)
	else:
		C = B - 1
		cnum1 = countone(C)
		if cnum1 > anum1:
			count += cnum1 - anum1
		elif cnum1 < anum1:
			count += 1
		else:
			count += 0
		count += 1
		print(count)


def val(a, b):
	if a == b:
		return 0
	elif b == 0 and a != 0:
		return -1
	elif b == 1:
		if a == 0:
			return 1
		else:
			return -1
	numb = bin(b - 1).count('1')
	numa = bin(a).count('1')
	if numb - numa + 1 >= 1:
		return numb - numa + 1
	else:
		return 2
t = int(input())
while t:
	t = t - 1
	(a, b) = input().split()
	(a, b) = (int(a), int(b))
	print(val(a, b))


def ones(n):
	o = 0
	while n:
		if n % 2:
			o += 1
		n //= 2
	return o
t = int(input())
while t:
	t -= 1
	(a, b) = input().split()
	if a == b:
		print(0)
		continue
	elif b == '0':
		print(-1)
		continue
	elif b == '1':
		if a == '0':
			print(1)
		else:
			print(-1)
		continue
	oa = ones(int(a))
	ob = ones(int(b) - 1)
	if oa > ob:
		print(2)
	else:
		print(ob - oa + 1)


for _ in range(int(input())):
	(A, B) = map(int, input().split())
	a = format(A, 'b')
	b = format(B, 'b')
	if A == B:
		print(0)
	elif B == 1 and A >= 1 or B == 0:
		print(-1)
	else:
		t = True
		s = 0
		i = -1
		while t:
			if b[i] == '0':
				s += 1
			else:
				t = False
			i -= 1
		a1 = a.count('1')
		b1 = b.count('1')
		if a1 > b1:
			if b1 - 1 + s == a1:
				print(1)
			elif a1 >= b1 - 1 + s:
				print(2)
			else:
				print(s - a1 + b1)
		elif a1 == b1:
			if b[-1] == '0':
				print(s)
			else:
				print(2)
		else:
			print(b1 - a1 + s)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	if a == b:
		print(0)
	elif b == 0:
		print(-1)
	elif b == 1 and a > 0:
		print(-1)
	else:
		ca = bin(a).count('1')
		cb = bin(b - 1).count('1')
		if cb > ca:
			print(cb - ca + 1)
		elif ca > cb:
			print(2)
		else:
			print(1)


for t in range(int(input())):
	(A, B) = map(int, input().split())
	if A == B:
		print(0)
	elif B == 0:
		print(-1)
	elif B == 1:
		if A == 0:
			print(1)
		else:
			print(-1)
	else:
		(a, b) = (bin(A).count('1'), bin(B - 1).count('1'))
		if a == b:
			print(1)
		elif a < b:
			print(b - a + 1)
		else:
			print(2)


def count1(n):
	count = 0
	while n > 0:
		count += n % 2
		n = n // 2
	return count
for t in range(int(input())):
	(a, b) = map(int, input().split())
	(oa, ob) = (count1(a), count1(b - 1))
	ans = 0
	if a == b:
		ans = 0
	elif b == 0:
		ans = -1
	elif b == 1:
		if a != 0:
			ans = -1
		else:
			ans = 1
	elif oa <= ob:
		ans = ob - oa + 1
	else:
		ans = 2
	print(ans)


t = int(input())
for test in range(t):
	(a, b) = map(int, input().split())
	if a == b:
		print(0)
		continue
	if a == 0 and b == 1:
		print(1)
		continue
	if b == 0 or b == 1:
		print('-1')
		continue
	b = b - 1
	aones = 0
	bones = 0
	x = a
	y = b
	while x > 0:
		if x % 2 == 1:
			aones += 1
		x = x // 2
	while y > 0:
		if y % 2 == 1:
			bones += 1
		y = y // 2
	ans = 1
	if aones < bones:
		ans += bones - aones
	elif aones > bones:
		ans += 1
	print(ans)


for i in range(int(input())):
	(a, b) = [int(x) for x in input().split()]
	if a == b:
		print(0)
		continue
	if b == 0 or (b == 1 and a != 0):
		print(-1)
		continue
	one_a = bin(a)[2:].count('1')
	one_b = bin(b - 1)[2:].count('1')
	if one_a > one_b:
		print(2)
	elif one_a <= one_b:
		print(one_b - one_a + 1)


def cnt(n):
	count = 0
	while n > 0:
		if n % 2 == 1:
			count += 1
		n = n // 2
	return count
t = int(input())
while t > 0:
	(a, b) = map(int, input().split())
	c = cnt(a)
	d = cnt(b - 1)
	if a == b:
		print(0)
	elif b == 0 or (b == 1 and a != 0):
		print(-1)
	elif c > d:
		print(2)
	else:
		print(d - c + 1)
	t -= 1


t = int(input())
for i in range(t):
	(a, b) = [int(i) for i in input().split()]
	if a == b:
		count = 0
	elif b == 0 and a != 0:
		count = -1
	elif b == 1 and a != 0:
		count = -1
	else:
		p1 = bin(a).count('1')
		p2 = bin(b - 1).count('1')
		if p1 > p2:
			count = 2
		if p2 >= p1:
			count = 1 + (p2 - p1)
	print(count)


cnt = lambda x: bin(x).count('1')

def solve(a, b):
	b_orig = b
	ans = 0
	if a == b:
		ans = 0
	elif a == b - 1:
		ans = 1
	elif b <= 1:
		ans = -1
	else:
		ans = abs(cnt(a) - cnt(b - 1)) + 1
	if cnt(a) > cnt(b - 1):
		ans = min(ans, 2)
	return ans
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	print(solve(a, b))


def calc(a, b):
	s1 = bin(a)[2:]
	s2 = bin(b - 1)[2:]
	if s1.count('1') > s2.count('1'):
		return 2
	elif s1.count('1') <= s2.count('1'):
		return s2.count('1') - s1.count('1') + 1
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	if a == b:
		print(0)
	elif b - a == 1:
		print(1)
	elif b == 0 and a >= 1:
		print(-1)
	elif b == 1 and a >= 1:
		print(-1)
	else:
		print(calc(a, b))


t = int(input())
while t > 0:
	t -= 1
	(a, b) = input().split(' ')
	(a, b) = (int(a), int(b))
	p = (b & -b).bit_length()
	if b == 0 and a != 0:
		print('-1')
	elif a == b:
		print('0')
	elif b == 1 and a != 0:
		print('-1')
	else:
		c1 = bin(a).count('1')
		c2 = bin(b - 1).count('1')
		m = c2 - c1 + 1
		if m <= 0:
			m = 2
		print(m)


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	if a == b:
		print(0)
	elif b == 0:
		print(-1)
	elif b == 1:
		if a == 0:
			print(1)
		else:
			print(-1)
	else:
		a1 = bin(a)
		ac = a1.count('1')
		b1 = bin(b - 1)
		bc = b1.count('1')
		if ac == bc:
			print(1)
		elif ac < bc:
			print(bc - ac + 1)
		elif ac > bc:
			print(2)


T = int(input())
for i in range(T):
	(a, b) = map(int, input().split(' '))
	to_get = b - 1
	counter_get = bin(to_get).count('1')
	counter_a = bin(a).count('1')
	counter_b = bin(a).count('1')
	if a == b:
		result = 0
	elif b == 0:
		if a == 0:
			result = 0
		else:
			result = -1
	elif b == 1:
		if a == 0:
			result = 1
		else:
			result = -1
	elif counter_get > counter_a:
		min_ops = counter_get - counter_a + 1
		result = min_ops
	elif counter_get < counter_a:
		min_ops = 1 + 1
		result = min_ops
	else:
		result = 1
	print(result)


for t in range(int(input())):
	(a, b) = input().split()
	(a, b) = (int(a), int(b))
	if a == b:
		print('0')
	elif b == 0:
		print(-1)
	elif b == 1:
		if a == 0:
			print(1)
		else:
			print(-1)
	else:
		a1 = bin(a)
		b1 = bin(b - 1)
		a1 = a1.count('1')
		b1 = b1.count('1')
		if a1 == b1:
			print(1)
		if a1 < b1:
			print(b1 - a1 + 1)
		if a1 > b1:
			print(2)


t = int(input())
for i in range(t):
	inp = input().split()
	a = int(inp[0])
	b = int(inp[1])
	if a == b:
		print(0)
	elif a == b - 1:
		print(1)
	elif b <= 1:
		print(-1)
	else:
		count1 = bin(a).count('1')
		count2 = bin(b - 1).count('1')
		if count1 == count2:
			print(1)
		elif count1 < count2:
			print(count2 - count1 + 1)
		elif count1 > count2:
			print(2)


t = int(input())
k = -1
for i in range(0, t):
	(a, b) = input().split()
	a = int(a)
	b = int(b)
	bq = b - 1
	c = bin(a)
	c = str(c)
	cc = bin(bq)
	cc = str(cc)
	a1 = c.count('1')
	a0 = c.count('0')
	b1 = cc.count('1')
	b0 = cc.count('0')
	if b == 0 and a != 0:
		k = -1
	elif a == b:
		k = 0
	elif b == 1 and a != 0:
		k = -1
	else:
		k = b1 - a1 + 1
		if k < 1:
			k = 2
	print(k)


t = int(input())
for cnt in range(t):
	(a, b) = input().split()
	(a, b) = [int(a), int(b)]
	if a == b:
		print(0)
	elif b <= 1 and a != 0:
		print(-1)
	else:
		binary = bin(a)
		setBits = [ones for ones in binary[2:] if ones == '1']
		countA = len(setBits)
		binary = bin(b)
		setBits = [ones for ones in binary[2:] if ones == '1']
		countB = len(setBits)
		for i in range(1, len(binary) - 1):
			if binary[-i] == '1':
				x = i - 1
				break
		countB = countB - 1 + x
		if countA <= countB:
			ans = countB - countA
			ans += 1
			print(ans)
		else:
			ans = 2
			print(ans)


import os, sys
n = int(input())
for i in range(n):
	(A, B) = list(map(int, input().split()))
	if A == B:
		print('0')
		continue
	elif B == 0:
		print('-1')
		continue
	elif B == 1:
		if A == 0:
			print('1')
		else:
			print('-1')
		continue
	A1 = bin(A).count('1')
	b1 = bin(B - 1).count('1')
	if A1 == b1:
		print('1')
	elif A1 > b1:
		print('2')
	else:
		print(str(b1 - A1 + 1))


T = int(input())
for i in range(T):
	(A, B) = map(int, input().split())
	Abin = str('{0:b}'.format(A))
	Bbin = str('{0:b}'.format(B - 1))
	count1B = Bbin.count('1')
	count1A = Abin.count('1')
	if B == 0:
		if A == 0:
			print(0)
		else:
			print(-1)
	elif A == B:
		print(0)
	elif B == 1:
		if A == 0:
			print(1)
		else:
			print(-1)
	elif count1A == count1B:
		print(1)
	elif count1A < count1B:
		print(1 + count1B - count1A)
	else:
		print(2)


t = int(input())
for i in range(t):
	(a, b) = list(map(int, input().split()))
	if a == b:
		print(0)
	elif b == 0 or (not a == 0 and b == 2 // 2):
		print(-1)
	else:
		if a - b + 1 == 0:
			print(1)
			continue
		b -= 1
		count = 0
		bina = bin(a)[2:]
		binb = bin(b)[2:]
		counta = bina.count('1')
		countb = binb.count('1')
		if countb == counta:
			print(2 // 2)
			continue
		if counta > countb:
			print(4 // 2)
		else:
			print(countb - counta + 1)


def Binary(dec):
	return bin(dec)[2:]

def counter(list01, list02):
	count11 = 0
	count12 = 0
	for i in range(0, len(list01)):
		if list01[i] == 1:
			count11 += 1
	for j in range(0, len(list02)):
		if list02[j] == 1:
			count12 += 1
	return [count11, count12]
t = int(input())
while t > 0:
	(a, b) = map(int, input().split())
	if a == b:
		count = 0
	elif b == 0:
		count = -1
	elif b == 1:
		if a == 0:
			count = 1
		else:
			count = -1
	else:
		alist = list(map(int, Binary(a)))
		blist = list(map(int, Binary(b - 1)))
		res = counter(alist, blist)
		if res[1] >= res[0]:
			count = res[1] - res[0] + 1
		else:
			count = 2
	print(count)
	t -= 1


def StringListToNumList(L):
	for i in range(0, len(L), 1):
		L[i] = int(L[i])
	return L

def NumberOfOnesInBinary(N):
	NumOfOnes = 0
	if N == 0:
		pass
	else:
		while N > 0:
			if N % 2 == 1:
				NumOfOnes += 1
			N = N // 2
	return NumOfOnes
T = int(input(''))
for k in range(0, T, 1):
	Numbers = input('')
	NumList = Numbers.split(' ')
	NumList = StringListToNumList(NumList)
	A = NumList[0]
	B = NumList[1]
	if A == B:
		print(0)
		continue
	elif A == 0 and B == 1:
		print(1)
		continue
	elif B == 0:
		print(-1)
		continue
	elif B == 1 and A != 0:
		print(-1)
		continue
	B = B - 1
	AOnes = NumberOfOnesInBinary(A)
	BOnes = NumberOfOnesInBinary(B)
	if BOnes == AOnes:
		print(1)
	elif BOnes < AOnes:
		print(2)
	else:
		print(BOnes - AOnes + 1)


a = int(input())
for _ in range(a):
	(b, c) = [int(i) for i in input().split()]
	if b == c:
		print(0)
	elif c == 1 and b == 0:
		print(1)
	elif c == 1 or c == 0:
		print(-1)
	else:
		c1 = c - 1
		b2 = bin(c1)[2:]
		b1 = bin(b)[2:]
		a1 = b1.count('1')
		a2 = b2.count('1')
		if a1 == a2:
			print(1)
		elif a1 < a2:
			print(a2 - a1 + 1)
		else:
			print(2)


for i in range(int(input())):
	(a, b) = (int(s) for s in input().split())
	s1 = bin(a)[2:]
	if a == b:
		print(0)
	elif b == 0:
		print(-1)
	elif b == 1:
		if a == 0:
			print(1)
		else:
			print(-1)
	else:
		s3 = bin(b - 1)[2:]
		c1 = s1.count('1')
		c3 = s3.count('1')
		if c3 < c1:
			ans1 = 1
		elif c3 == c1:
			ans1 = 0
		else:
			ans1 = c3 - c1
		print(ans1 + 1)


def ones(a):
	res = 0
	while a:
		res += a % 2
		a = a // 2
	return res

def counting(a, b):
	if a == b:
		return 0
	elif b == 0:
		return -1
	elif b == 1:
		return 1 if a == 0 else -1
	ops = ones(b - 1) - ones(a) + 1
	return ops if ops > 0 else 2
for i in range(int(input())):
	(j, k) = list(map(int, input().split()))
	print(counting(j, k))


import itertools

def bruteForceMethod(A, B):
	if B == 0:
		return -1
	if A != 0 and B == 1:
		return -1
	if A == B:
		return 0
	if A + 1 == B:
		return 1
	A_ = bin(A)[2:]
	B_ = bin(B)[2:]
	(digitsToCheck, newDigitsFormed) = ({A}, set())
	iterationsMade = 0
	while True:
		iterationsMade += 1
		onesSeen = set()
		for a in digitsToCheck:
			a = bin(a)[2:]
			ones = a.count('1')
			if ones in onesSeen:
				continue
			else:
				onesSeen.add(ones)
			for leadingZeroes in range(0, max(0, 10 - len(a)) + 1):
				newDigitLength = len(a) + leadingZeroes
				for k in itertools.combinations(range(newDigitLength), ones):
					newDigitFormed = ['0'] * newDigitLength
					for i in k:
						newDigitFormed[i] = '1'
					newDigitFormed = ''.join(newDigitFormed)
					newDigitFormed = int(newDigitFormed, 2) + 1
					newDigitsFormed.add(newDigitFormed)
		if B in newDigitsFormed:
			return iterationsMade
		elif iterationsMade > 9:
			return -1
		else:
			(digitsToCheck, newDigitsFormed) = (newDigitsFormed, set())

def clearMethod(A, B):
	if A == B:
		return 0
	if A + 1 == B:
		return 1
	if A != 0 and B == 0:
		return -1
	if (A != 0 and A != 1) and B == 1:
		return -1
	A = bin(A)[2:]
	B = bin(B)[2:]
	A1 = A.count('1')
	B1 = B.count('1')
	if B[-1] == '1':
		if A1 < B1:
			return B1 - A1
		elif A1 + 1 == B1:
			return 1
		elif A1 >= B1:
			return 2
	elif B[-1] == '0':
		B = bin(int(B, 2) - 1)[2:]
		B1 = B.count('1')
		if A1 < B1:
			return B1 - A1 + 1
		elif A1 == B1:
			return 1
		elif A1 >= B1:
			return 2
T = int(input())
for _ in range(T):
	(A, B) = [int(x) for x in input().split()]
	print(clearMethod(A, B))


t = int(input())
for i in range(t):
	z = input().split()
	z = [int(j) for j in z]
	a = bin(z[0])[2:]
	b = bin(z[1])[2:]
	rev = b[::-1]
	c = 0
	for l in rev:
		if l == '1':
			break
		else:
			c += 1
	c1 = 0
	c1 = a.count('1')
	c2 = b.count('1')
	if z[0] == z[1]:
		print(0)
	elif z[1] == 0:
		print(-1)
	elif z[1] == 1:
		if z[0] == 0:
			print(1)
		else:
			print(-1)
	else:
		p = c2 - c1 + c
		if p > 0:
			print(p)
		else:
			print(2)


def f(a, b):
	n1 = '{0:b}'.format(a)
	n2 = '{0:b}'.format(b - 1)
	(c1, c2) = (n1.count('1'), n2.count('1'))
	if c2 >= c1:
		return 1 + c2 - c1
	return 2
t = int(input())
for x1 in range(t):
	(a, b) = map(int, input().split())
	if a == b:
		ans = 0
	elif a == 0 and b == 1:
		ans = 1
	elif b == 0 or b == 1:
		ans = -1
	else:
		ans = f(a, b)
	print(ans)


def convert(n):
	if n == 0:
		return 0
	else:
		return (n & 1) + convert(n >> 1)
t = int(input())
for i in range(0, t):
	s = input().split()
	a = int(s[0])
	b = int(s[1])
	if a == b:
		print('0')
	elif a > 0 and b == 1:
		print('-1')
	elif b == 0:
		print('-1')
	else:
		c = b - 1
		A = convert(a)
		B = convert(c)
		if A < B:
			count = 1 + B - A
		elif A == B:
			count = 1
		else:
			count = 2
		print(count)


t = int(input().strip())
for _ in range(t):
	(a, b) = map(int, input().strip().split())
	d = b - a
	b_a = bin(a)
	b_b = bin(b)
	b_a = b_a[2:]
	b_b = b_b[2:]
	one_a = b_a.count('1')
	one_b = b_b.count('1')
	if d == 0:
		print('0')
	elif d == 1:
		print('1')
	elif b == 0 or b == 1:
		print('-1')
	elif one_a > one_b:
		if b % 2 == 0:
			b_b = bin(b - 1)
			b_b = b_b[2:]
			one_b = b_b.count('1')
			if one_a > one_b:
				print(2)
			elif d > 0:
				print(min(d, one_b - one_a + 1))
			else:
				print(one_b - one_a + 1)
		else:
			print(2)
	elif one_a == one_b:
		if b_b[len(b_b) - 1] == '0':
			if b_b[len(b_b) - 2] == '1':
				print('1')
			else:
				b_b = bin(b - 1)
				b_b = b_b[2:]
				one_b = b_b.count('1')
				if d > 0:
					print(min(d, one_b - one_a + 1))
				else:
					print(one_b - one_a + 1)
		else:
			print(2)
	elif b & 1:
		if d > 0:
			print(min(d, one_b - one_a))
		else:
			print(one_b - one_a)
	else:
		b_b = bin(b - 1)
		b_b = b_b[2:]
		one_b = b_b.count('1')
		if d > 0:
			print(min(d, one_b - one_a + 1))
		else:
			print(one_b - one_a + 1)


def countSetBits(num):
	binary = bin(num)
	setBits = [ones for ones in binary[2:] if ones == '1']
	return len(setBits)
t = int(input())
for _ in range(t):
	(A, B) = [int(x) for x in input().split()]
	set_A = countSetBits(A)
	set_B = countSetBits(B - 1)
	if A == B:
		print('0')
	elif A > 1 and B < 2 or (A == 1 and B == 0):
		print('-1')
	elif set_B < set_A:
		print('2')
	else:
		ans = set_B - set_A + 1
		print(ans)


t = input()
t = int(t)
for i in range(0, t):
	cnt = 0
	(a, b) = map(int, input().split())
	if a == b:
		print(0)
		continue
	if a == 0 and b == 1:
		print(1)
		continue
	if b <= 1:
		print(-1)
		continue
	b = b - 1
	ba = list(map(int, list(bin(b))[2:]))
	aa = list(map(int, list(bin(a))[2:]))
	b_cnt = ba.count(1)
	a_cnt = aa.count(1)
	if a_cnt < b_cnt:
		print(b_cnt - a_cnt + 1)
	elif b_cnt < a_cnt:
		print(2)
	elif b_cnt == a_cnt:
		print(1)


def fn(n):
	b = '{0:b}'.format(n)
	return b.count('1')

def bins(a, b):
	if a == b:
		return 0
	if b == 0:
		return -1
	if b == 1:
		if a == 0:
			return 1
		else:
			return -1
	c = fn(b - 1) - fn(a) + 1
	if c > 0:
		return c
	else:
		return 2
nTestCases = int(input())
while nTestCases > 0:
	(a, b) = input().split()
	(a, b) = (int(a), int(b))
	print(bins(a, b))
	nTestCases -= 1


def bin1(x):
	res = 0
	while x > 0:
		res += x % 2
		x = x // 2
	return res
for t in range(int(input())):
	(a, b) = map(int, input().split())
	if b == a:
		print(0)
	elif b == 0:
		print(-1)
	else:
		cta = bin1(a)
		ctb = bin1(b - 1)
		if cta > ctb:
			if ctb == 0:
				print(-1)
			else:
				print(2)
		else:
			print(ctb - cta + 1)


def main():
	for _ in range(int(input())):
		(a, b) = [int(x) for x in input().split()]
		bina = bin(a)[2:]
		binb = bin(b)[2:]
		binac = bina.count('1')
		binbc = binb.count('1')
		extra = binac - binbc
		revidx = binb[::-1].index('1') if b != 0 else 0
		ans = 0
		if a == b:
			ans = 0
		elif b == 0 and a != 0:
			ans = -1
		elif b == 1 and a > 1:
			ans = -1
		elif b == 1 and a == 0:
			ans = 1
		elif extra < 0:
			ans = revidx - extra
		elif extra == 0:
			if binb[-1] == '0':
				ans = revidx
			else:
				ans = 2
		elif revidx > extra:
			ans = revidx - extra
		else:
			ans = 2
		print(ans)
main()


for testc in range(int(input())):
	(aa, bb) = map(int, input().split())
	b = '{0:b}'.format(bb)
	a = '{0:b}'.format(aa)
	na = a.count('1')
	nb = b.count('1')
	b = '0' * 60 + b
	l = len(b)
	odd = False
	if bb % 2 != 0:
		odd = True
	if nb == 0 and na != 0:
		print('-1')
	elif bb == 1 and (aa != 0 or aa != 1):
		if aa == 0:
			print('1')
		elif aa == 1:
			print('0')
		else:
			print('-1')
	elif na > nb:
		diff = na - nb + 1
		one = 0
		l = l - 1
		while b[l] == '0':
			l = l - 1
			one += 1
		if one == diff:
			print('1')
		elif one < diff:
			print('2')
		else:
			print(one - diff + 1)
	elif nb > na:
		diff = nb - na - 1
		if odd:
			print(diff + 1)
		else:
			one = 0
			l = l - 1
			while b[l] == '0':
				l = l - 1
				one += 1
			print(one + 1 + diff)
	elif aa == bb:
		print('0')
	elif odd:
		print('2')
	else:
		one = 0
		l = l - 1
		while b[l] == '0':
			l = l - 1
			one += 1
		print(one)


t = int(input())
for test in range(t):
	(a, b) = map(int, input().split())
	ans = -1
	if a == b:
		ans = 0
	elif a == 0 and b == 1:
		ans = 1
	elif b > 1:
		counta = 0
		while a > 0:
			if a & 1:
				counta += 1
			a >>= 1
		countb = 0
		index = -2
		flag = 0
		while b > 0:
			if flag == 0:
				index += 1
			if b & 1:
				flag = 1
				countb += 1
			b >>= 1
		index += 1
		if countb <= counta and index <= counta - countb:
			ans = 2
		else:
			ans = countb - counta + index
	print(ans)


T = int(input())
for i in range(T):
	(A, B) = list(map(int, input().strip().split(' ')))
	C = B - 1
	D = '{0:08b}'.format(A)
	C = '{0:08b}'.format(C)
	a1 = D.count('1')
	b1 = C.count('1')
	if B == 1 and A > 1:
		print(-1)
	elif a1 > b1 and A != B and (A != 0) and (B != 0):
		print(2)
	elif B == 0 and A != 0:
		print(-1)
	elif B == 1 and A != 0 and (A != 1):
		print(-1)
	elif A == B:
		print(0)
	else:
		c = b1 - a1 + 1
		print(c)


t = int(input())

def f(A, B):
	str_A = bin(A)[2:]
	str_B = bin(B - 1)[2:]
	lhs = str_A.count('1')
	rhs = str_B.count('1')
	if A == B:
		return 0
	if B == 0:
		return -1
	if B == 1:
		if A == 0:
			return 1
		else:
			return -1
	if lhs == rhs:
		return 1
	elif lhs < rhs:
		return rhs - lhs + 1
	else:
		return 2
for _ in range(t):
	(A, B) = map(int, input().split())
	print(f(A, B))


t = int(input())
i = 0
while i < t:
	(a, b) = [int(j) for j in input().split()]
	if a == b:
		print('0')
	elif b == 0:
		print('-1')
	elif b == 1:
		if a != 0:
			print('-1')
		else:
			print('1')
	else:
		a1 = 0
		b1 = 0
		while a > 0:
			if a % 2 == 1:
				a1 = a1 + 1
			a = a // 2
		b = b - 1
		while b > 0:
			if b % 2 == 1:
				b1 = b1 + 1
			b = b // 2
		if a1 <= b1:
			print(b1 - a1 + 1)
		elif a1 > b1:
			print('2')
	i = i + 1


def dtb(n):
	g = bin(n)
	k = len(g)
	m = g[2:k]
	return int(m)

def jkl(p):
	c = 0
	while p != 0:
		if p % 10 == 1:
			c = c + 1
		p = p // 10
	return c
t = int(input())
for i in range(0, t):
	(a, b) = map(int, input().split())
	if b == a:
		print(0)
	elif b == 0:
		print(-1)
	elif b == 1 and a > b:
		print(-1)
	else:
		aa = jkl(dtb(a))
		bb = jkl(dtb(b - 1))
		if bb < aa:
			print(2)
		elif bb == aa:
			print(1)
		else:
			print(1 + (bb - aa))


def sb(num):
	binary = bin(num)
	setBits = [ones for ones in binary[2:] if ones == '1']
	return len(setBits)

def doIt(x, y):
	if x == y:
		return 0
	if y == 0:
		return -1
	if y == 1:
		if x == 0:
			return 1
		return -1
	kachra = sb(y - 1) - sb(x) + 1
	if kachra > 0:
		return kachra
	else:
		return 2

def main():
	t = int(input())
	for _ in range(t):
		(a, b) = map(int, input().split())
		print(doIt(a, b))
main()


a = int(input())
for i in range(a):
	qq = list(map(int, input().split()))
	a = qq[0]
	b = qq[1]
	if a == b:
		print(0)
	elif b == 0 or (b == 1 and a != 0):
		print(-1)
	elif b == 1 and a == 1:
		print(1)
	else:
		b = b - 1
		a = a
		q1 = bin(b)[2:].count('1') - bin(a)[2:].count('1') + 1
		if q1 <= 0:
			print('2')
		else:
			print(q1)


def binary(n):
	a = 0
	while n != 0:
		k = n % 2
		if k == 1:
			a += 1
		n = n // 2
	return a
T = int(input())
for i in range(T):
	(a, b) = map(int, input().split())
	if a == b:
		print(0)
	elif b == 0 or (a != 0 and b == 1):
		print(-1)
	else:
		A = binary(a)
		B = binary(b - 1)
		if A > B:
			print(2)
		elif A == B:
			print(1)
		else:
			print(B - A + 1)


t = int(input())
while t:
	(a, b) = map(int, input().split(' '))
	f = 0
	if a == b:
		print(0)
	elif a == 0 and b == 1:
		print(1)
	elif b == 0 or b == 1:
		print(-1)
	else:
		f = f + 1
		b = b - 1
		x = 0
		y = 0
		while a:
			if a % 2:
				x += 1
			a = a // 2
		while b:
			if b % 2:
				y += 1
			b = b // 2
		if x < y:
			f = f + y - x
		elif x > y:
			f = f + 1
		print(f)
	t = t - 1


for t in range(int(input())):
	(a, b) = list(map(int, input().split()))
	(bin_a, bin_b) = ('{0:b}'.format(a), '{0:b}'.format(b))
	(a_one, b_one) = (list(bin_a).count('1'), list(bin_b).count('1'))
	(len_a, len_b) = (len(bin_a), len(bin_b))
	tr_zero = 0
	pos = -1
	while pos > -1 * len(bin_b):
		if bin_b[pos] == '0':
			tr_zero += 1
			pos -= 1
		else:
			break
	b_one = b_one + tr_zero
	diff = b_one - a_one
	if a == b:
		print(0)
	elif b == 1 and a != 0 and (a != 1):
		print(-1)
	elif b == 0 and a != 0:
		print(-1)
	elif b_one > a_one:
		print(diff)
	elif b_one <= a_one:
		print(2)


t = int(input())
for z in range(t):
	[a, b] = [int(j) for j in input().split()]
	if a == b:
		print(0)
	elif a == b - 1:
		print(1)
	elif b == 0:
		print(-1)
	elif b == 1 and a != 0:
		print(-1)
	else:
		b = b - 1
		n1 = bin(a)[2:].count('1')
		n2 = bin(b)[2:].count('1')
		if n1 < n2:
			print(1 + n2 - n1)
		elif n1 == n2:
			print(1 + 0)
		else:
			print(1 + 1)


T = int(input())
for f in range(T):
	inp = list(map(int, input().split()))
	a = inp[0]
	b = inp[1]
	if a == b:
		ans = 0
	elif b == 1 and a > 0:
		ans = -1
	elif b == 0:
		ans = -1
	else:
		b = b - 1
		bbin = bin(b)
		abin = bin(a)
		b1 = bbin.count('1')
		a1 = abin.count('1')
		val = b1 - a1 + 1
		if val > 0:
			ans = val
		else:
			ans = 2
	print(ans)


t = int(input())
for j in range(t):
	(a, b) = [int(x) for x in input().split()]
	cnta1 = 0
	a1 = bin(a)[2:]
	b1 = bin(b)[2:]
	cntb1 = 0
	for i in a1:
		if i == '1':
			cnta1 += 1
	for i in b1:
		if i == '1':
			cntb1 += 1
	fap = 0
	for i in range(1, len(b1) + 1, 1):
		if b1[-i] == '1':
			fap = i
			break
	if b == 0 or b == 1:
		if b == 0:
			if a:
				print(-1)
			else:
				print(0)
		if b == 1:
			if a < 2:
				print(b - a)
			else:
				print(-1)
	elif cnta1 == cntb1:
		if b % 2:
			if b >= a:
				print(min(2, b - a))
			else:
				print(2)
		elif b >= a:
			print(min(b - a, fap - 1))
		else:
			print(fap - 1)
	elif cnta1 < cntb1:
		print(cntb1 - 1 - cnta1 + fap)
	elif cnta1 - cntb1 + 1 == fap - 1:
		print(1)
	elif cnta1 - cntb1 + 1 < fap - 1:
		print(1 + fap - cnta1 + cntb1 - 2)
	else:
		print(2)


def dbin(x):
	return int(bin(x)[2:])

def dbin1(x):
	return bin(x)[2:]

def print1(x):
	if x > 0:
		print(x)
	else:
		x = 1
		print(x + 1)

def zero(x):
	flag = 0
	count = 0
	while flag == 0 and x > 0:
		if x % 10 != 0:
			flag = 1
		else:
			count = count + 1
			x = x // 10
	return count
T = int(input())
for i in range(T):
	n1 = input()
	n2 = list(map(int, n1.split()))
	A1 = n2[0]
	B1 = n2[1]
	A = dbin(A1)
	B = dbin(B1)
	A1 = dbin1(A1)
	B1 = dbin1(B1)
	if n2[0] == n2[1]:
		print(0)
	elif n2[1] == 1 and n2[0] == 0:
		print(1)
	elif n2[1] == 1 or n2[1] == 0:
		print(-1)
	else:
		oneB = B1.count('1')
		oneA = A1.count('1')
		if oneA < oneB:
			print(oneB - oneA + zero(B))
		elif oneA > oneB:
			B1 = dbin1(n2[1] - 1)
			oneB = B1.count('1')
			print1(oneB - oneA + 1)
		else:
			B1 = dbin1(n2[1] - 1)
			output = B1.count('1') - A1.count('1') + 1
			print1(output)


x = int(input())
for i in range(x):
	z = input()
	z = z.split(' ')
	a = int(z[0])
	b = int(z[1])
	if a == b:
		print(0)
	elif b == 0:
		print(-1)
	elif b == 1:
		if a == 0:
			print(1)
		else:
			print(-1)
	else:
		s = bin(b - 1)[2:].count('1') - bin(a)[2:].count('1') + 1
		if s <= 0:
			print(2)
		else:
			print(s)


def no_of_ending_zeros(r):
	z = 0
	for i in range(len(r) - 1, -1, -1):
		if r[i] == '0':
			z = z + 1
		if r[i] == '1':
			break
	return z
for _ in range(int(input())):
	(N1, N2) = map(int, input().split())
	A = format(N1, 'b')
	B = format(N2, 'b')
	p = -1
	nez = no_of_ending_zeros(B)
	if A != '0' and B == '0' or (B == '1' and A != '1' and (A != '0')):
		print(p)
		continue
	if A == B:
		p = 0
	elif A.count('1') < B.count('1'):
		if nez == 0:
			p = B.count('1') - A.count('1')
		else:
			p = B.count('1') - A.count('1') + nez
	elif A.count('1') == B.count('1'):
		if nez == 0:
			p = 2
		else:
			p = nez
	elif A.count('1') > B.count('1'):
		if nez == 0:
			p = 2
		elif nez >= A.count('1') - B.count('1') + 1:
			p = nez - (A.count('1') - B.count('1') + 1) + 1
		else:
			p = 2
	print(p)


t = int(input())
for i in range(t):
	(a, b) = [int(i) for i in input().split()]
	if a == b:
		print('0')
	elif b == 1 and a > 1 or (b == 0 and a != 0):
		print('-1')
	else:
		(na, nb) = (0, 0)
		res = 0
		j = a
		while j != 0:
			j = j & j - 1
			na += 1
		j = b
		while j != 0:
			j = j & j - 1
			nb += 1
		if b % 2 == 1:
			if nb > na:
				res = nb - na
			else:
				res = 2
		else:
			x = 2
			exp = 0
			while b % x == 0:
				x *= 2
				exp += 1
			if nb > na:
				res = nb - na + exp
			elif exp == na - (nb - 1):
				res = 1
			elif exp > na - (nb - 1):
				res = exp - na + nb
			else:
				res = 2
		if b < a:
			print(res)
		elif b - a < res:
			print(b - a)
		else:
			print(res)


t = int(input())
for i in range(t):
	(a, b) = [int(i) for i in input().split()]
	bin_a = bin(a)
	bin_b = bin(b)
	na = bin_a.count('1')
	nb = bin_b.count('1')
	if a == b:
		print(0)
	elif a == 0 and b == 1:
		print(1)
	elif b == 1 or b == 0:
		print(-1)
	elif na == nb:
		c = 0
		if bin_b.endswith('1'):
			print(2)
		else:
			for j in bin_b[::-1]:
				if j != '1':
					c += 1
				else:
					break
			print(c)
	elif na < nb:
		c = 0
		for j in bin_b[::-1]:
			if j != '1':
				c += 1
			else:
				break
		print(nb - na + c)
	else:
		c = 0
		bn = bin(b - 1)
		bnn = bn.count('1')
		ans = bnn - na + 1
		if ans > 0:
			print(ans)
		else:
			print(2)


t = int(input())
while t:
	t = t - 1
	s = input().split()
	a = int(s[0])
	b = int(s[1])
	if a == b:
		print(0)
		continue
	if b == 0 or (b == 1 and a != 0):
		print(-1)
		continue
	x = bin(a).count('1')
	k = bin(b).count('1') + list(reversed(bin(b))).index('1') - 1
	if k == x:
		print(1)
	if k > x:
		print(k - x + 1)
	if k < x:
		print(2)


for _ in range(int(input().strip())):
	(a, b) = map(int, input().split())
	if a == b:
		print('0')
	elif b == 0:
		print('-1')
	elif b == 1:
		if a == 0:
			print('1')
		else:
			print('-1')
	else:
		c = 0
		c1 = 0
		d = 0
		d1 = 0
		dec = 1
		if a == 0:
			c = 0
		while a > 0:
			c1 = c1 + (a & 1)
			if dec == 1:
				if a & 1:
					dec = 0
				else:
					c += 1
			a = a // 2
		dec = 1
		if b == 0:
			d = 1
		while b > 0:
			d1 = d1 + (b & 1)
			if dec == 1:
				if b & 1:
					dec = 0
				else:
					d += 1
			b = b // 2
		r = d + d1 - c1
		if r > 0:
			print(r)
		else:
			print('2')


T = int(input())
for t in range(T):
	(A, B) = map(int, input().split())
	if B == 0:
		if A == 0:
			print(0)
		else:
			print(-1)
	elif B == 1:
		if A == 0:
			print(1)
		elif A == 1:
			print(0)
		else:
			print(-1)
	elif A == B:
		print(0)
	else:
		binB = bin(B - 1)
		binA = bin(A)
		ctbinA = str(binA).count('1')
		ctbinB = str(binB).count('1')
		if ctbinA == ctbinB:
			print(1)
		elif ctbinA > ctbinB:
			print(2)
		else:
			print(ctbinB - ctbinA + 1)


test_case = int(input())

def count_zero_one(num):
	arr = [0, 0]
	for n in num:
		if n == 0:
			arr[0] += 1
		elif n == 1:
			arr[1] += 1
	return arr
while test_case:
	(a, b) = input().split()
	a = int(a)
	b = int(b)
	if a == b:
		print(0)
	elif a == 0 and b == 1:
		print(1)
	elif b == 0:
		print(-1)
	elif b == 1 and (not a == 0):
		print(-1)
	else:
		b = b - 1
		a_bin = list(map(int, bin(a)[2:]))
		b_bin = list(map(int, bin(b)[2:]))
		if len(a_bin) < len(b_bin):
			diff = len(b_bin) - len(a_bin)
			a_bin = [0] * diff + a_bin
		result = count_zero_one(b_bin)[1] - count_zero_one(a_bin)[1] + 1
		if result > 0:
			print(result)
		else:
			print(2)
	test_case = test_case - 1