Chef has two integers X and Y. Chef wants to perform some operations to make both X and Y zero simultaneously. In one operation, Chef can either:
set X := 2 \cdot X
or set Y := 2 \cdot Y
or set X := X - 1 and Y := Y - 1

Chef is a little busy with preparing the contest. Help him find the minimum number of operations required to make both X and Y equal to 0 simultaneously. If it is impossible to do so after any number of operations, print -1.

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

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first and only line of each test case contains two space separated integers X and Y.

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

For each test case, print the minimum number of operations required to make X and Y zero simultaneously. If it is impossible to do so after any number of operations, print -1 instead.

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

$1 ≤ T ≤ 3 \cdot 10^{5}$
$0 ≤ X , Y ≤ 10^{18}$

----- Sample Input 1 ------ 
2
1 2
99999999999999999 99999999999999999
----- Sample Output 1 ------ 
3
99999999999999999
----- explanation 1 ------ 
Let $(x, y)$ denote the values of $X$ and $Y$ respectively.

Test case 1: Three operations are required: $(1, 2) \xrightarrow{X := X \cdot 2}{} (2, 2) \xrightarrow[Y := Y - 1]{X := X - 1} (1, 1) \xrightarrow[Y := Y - 1]{X := X - 1} (0, 0)$

It can be proven that it is impossible in fewer operations.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Mathematics

Ad-hoc

Starter code:

Solutions:
import math
for i in range(int(input())):
	(X, Y) = map(int, input().split())
	p = max(X, Y)
	q = X + Y - p
	if q != 0:
		c = int(math.log2(p / q))
		a = q
		for j in range(c):
			a *= 2
		if a != p:
			c += 1
		print(c + p)
	elif p == 0 and q == 0:
		print(0)
	else:
		print(-1)


import sys
from math import gcd, sqrt, log, ceil, floor
tc = int(input().strip())
for t in range(tc):
	(x, y) = map(int, input().split())
	if x == y:
		print(x)
		continue
	if x == 0 or y == 0:
		print(-1)
		continue
	ops = 0
	if min(x, y) == y:
		(x, y) = (y, x)
	ops = int(log(y / x, 2))
	if x * pow(2, ops) != y:
		ops += 1
	ops += y
	print(ops)


try:
	for _ in range(int(input())):
		(x, y) = map(int, input().split())
		if x != y and x * y == 0:
			print(-1)
		else:
			if x > y:
				(x, y) = (y, x)
			(X, Y) = (len(bin(x)[:]), len(bin(y)[:]))
			l = Y - X
			x = x << l
			res = l + y
			if x < y:
				res += 1
			print(res)
except:
	pass


from math import log2, ceil

def soln(x, y):
	if x == 0 and y == 0:
		return 0
	if x == 0 or y == 0:
		return -1
	if x == y:
		return x
	elif x > y:
		return ceil(log2(x / y)) + x
	else:
		return ceil(log2(y / x)) + y
	return -1
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	print(int(soln(x, y)))


for _ in range(int(input())):
	(A, B) = map(int, input().split())
	if A == B:
		print(A)
	elif A == 0 or B == 0:
		print(-1)
	else:
		res = 0
		mn = min(A, B)
		mx = max(A, B)
		while mn < mx:
			mn *= 2
			res += 1
		print(res + mx)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	if x < y:
		(x, y) = (y, x)
	cun = 0
	if y == 0 and x > 0:
		print(-1)
	else:
		while y < x:
			y *= 2
			cun += 1
		print(cun + x)


def getres(x, y):
	count = 0
	while y >= x * 2:
		x *= 2
		count += 1
	if x == y:
		print(count + y)
	else:
		print(count + y + 1)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	if a == 0 and b == 0:
		print(0)
	elif a == 0 or b == 0:
		print(-1)
	elif a > b:
		getres(b, a)
	else:
		getres(a, b)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	if a == 0 and b == 0:
		print(0)
	elif a == 0 or b == 0:
		print(-1)
	else:
		steps = 0
		while b >= a * 2:
			a *= 2
			steps += 1
		while a >= 2 * b:
			b *= 2
			steps += 1
		if a != b:
			steps += 1
		print(max(a, b) + steps)


t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	if x > y:
		(x, y) = (y, x)
	if x == 0 and y == 0:
		print(0)
	elif x == 0:
		print(-1)
	else:
		steps = 0
		while x < y:
			x *= 2
			steps += 1
		print(steps + y)


for x in range(int(input())):
	(x, y) = map(int, input().split())
	if x > y:
		(x, y) = (y, x)
	if x == 0 and y == 0:
		print(0)
	elif x == 0:
		print(-1)
	else:
		ans = 0
		while x < y:
			x *= 2
			ans += 1
		print(ans + y)


import math
t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	if x == y == 0:
		print(0)
	elif x == 0 or y == 0:
		print(-1)
	else:
		n = min(x, y)
		m = max(x, y)
		c1 = math.floor(math.log(m / n, 2))
		c2 = math.log(m / n, 2)
		if c1 == c2:
			print(c1 + m)
		else:
			ans = math.floor(math.log(m / n, 2))
			ans += m + 1
			print(ans)


import math
t = int(input())
for i in range(t):
	[X, Y] = [int(i) for i in input().split()]
	if X == Y == 0:
		print(0)
	elif X == 0 or Y == 0:
		print(-1)
	else:
		N = min(X, Y)
		M = max(X, Y)
		info1 = math.floor(math.log(M / N, 2))
		info2 = math.log(M / N, 2)
		if info1 == info2:
			print(info1 + M)
		else:
			ans = math.floor(math.log(M / N, 2))
			ans += M + 1
			print(ans)


T = int(input())
for _ in range(T):
	(x, y) = map(int, input().split())
	if x > y:
		(x, y) = (y, x)
	if x == y:
		print(x)
		continue
	if y == 0 or x == 0:
		print(-1)
		continue
	else:
		c = 0
		while x * 2 <= y:
			x = x * 2
			c += 1
		if x == y:
			print(y + c)
			continue
		temp = y - x
		c += x - temp
		x = temp
		c += x * 2 + 1
		print(c)


for i in range(int(input())):
	l = list(map(int, input().split()))
	l = sorted(l)
	x = l[0]
	y = l[1]
	if x == 0 and y == 0:
		print(0)
	elif x == 0:
		print(-1)
	elif x != 0 and y != 0:
		a = 0
		while x < y:
			x = x * 2
			a += 1
		print(a + y)


for _ in range(int(input())):
	(x, y) = list(map(int, input().split()))
	if x == y:
		print(x)
	elif x == 0 or y == 0:
		print(-1)
	else:
		ma = max(x, y)
		mi = min(x, y)
		op = 0
		while mi <= ma:
			mi *= 2
			op += 1
		op -= 1
		mi /= 2
		if mi == ma:
			print(op + ma)
		else:
			print(ma + op + 1)


from collections import defaultdict
from collections import Counter
import math
import bisect

class dsu:

	def __init__(self):
		self.parent = defaultdict(int)
		self.size = [0] * (n + 1)

	def start(self):
		for i in range(1, n + 1):
			self.parent[i] = i

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u != v:
			self.parent[v] = u

	def treeinput(self, m):
		for i in range(m):
			(u, v) = map(int, input().split())
			self.union(u, v)

	def printt(self):
		print(self.parent)

def setbit(arr):
	mask = 1
	bit = [0] * 32
	for i in range(32):
		for k in arr:
			if k & mask:
				bit[i] += 1
		mask <<= 1
	return bit

def prefix_sum(nums):
	prefix = [0]
	for i in range(len(nums)):
		prefix.append(prefix[-1] + nums[i])
	return prefix

def mx_lensubarray(nums):
	res = 0
	j = 0
	mp = defaultdict(int)
	prefix = prefixsum(nums)
	mxSum = 0
	for i in range(len(nums)):
		if nums[i] in mp:
			temp = mp[nums[i]]
		else:
			temp = 0
		j = max(temp, j)
		mp[nums[i]] = i + 1
		res = max(res, i - j + 1)
		mxSum = max(mxSum, prefix[i + 1] - prefix[j])
	return res

def lenOfLongSubarr(self, A, N, k):
	mp = {}
	sm = 0
	mxlen = 0
	for i in range(N):
		sm += A[i]
		if sm == k:
			mxlen = i + 1
		if sm - k in mp:
			mxlen = max(mxlen, i - mp[sm - k])
		if sm not in mp:
			mp[sm] = i
	return mxlen

def no_of_factor(s):
	while i <= s ** 0.5:
		if not s % i:
			cnt = cnt + 1 if s / i == i else cnt + 2
	i += 1
	return cnt

def primes(n):
	arr = []
	i = 2
	while i * i <= n:
		if not n % i:
			cnt = 0
			while not n % i:
				cnt += 1
				n //= i
			arr.append([i, cnt])
		i += 1
	if n > 1:
		arr.append([n, 1])
	return arr

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	res = []
	for i in range(2, n + 1):
		if prime[i]:
			res.append(i)
	return res

def treeinput():
	adj = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		adj[u].append(v)
		adj[v].append(u)

def dfs_size(node, parent):
	sum_size[node] = 1
	for child in adj[node]:
		if child != parent:
			dfs_size(child, node)
			sum_size[node] += sum_size[child]

def anda(arr):
	res = arr[0]
	for i in arr:
		res &= i
	return res

def ora(arr):
	res = arr[0]
	for i in arr:
		res |= i
	return res

def xora(arr):
	res = 0
	for i in arr:
		res ^= i
	return res

def ispowerof2(n):
	return (n != 0) & (n & n - 1 == 0)
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	if x < y:
		(x, y) = (y, x)
	ans = 0
	if y == 0 and x > 0:
		print(-1)
	else:
		while y < x:
			y *= 2
			ans += 1
		print(ans + x)


for T in range(int(input())):
	(x, y) = map(int, input().split())
	counter = 0
	x = [x, y]
	x.sort()
	y = x[0]
	x = x[1]
	if y == x:
		print(x)
		continue
	if y == 0:
		print(-1)
		continue
	while x != y:
		while 2 * y <= x:
			counter += 1
			y = y * 2
		verschil = x - y
		stappen = y - verschil
		x -= stappen
		y -= stappen
		counter += stappen
	print(int(counter + x))


for i in range(int(input())):
	(a, b) = map(int, input().split())
	(a, b) = (max(a, b), min(a, b))

	def solve(a, b):
		if a == b:
			return a
		if a == 0 and b == 0:
			return 0
		if a == 0 or b == 0:
			return -1
		ans = 0
		while b <= a:
			b *= 2
			ans += 1
		b = b // 2
		ans -= 1
		diff = a - b
		if diff == 0:
			return ans + a
		x = b - diff
		b -= x
		a -= x
		ans += x
		ans += 1
		ans += a
		return ans
	print(solve(a, b))


for i in range(int(input())):
	(x, y) = map(int, input().split())
	if x == y:
		print(x)
	else:
		mx = max(x, y)
		mi = min(x, y)
		if mi == 0:
			print(-1)
			continue
		c = 0
		if mi <= mx // 2:
			while mi <= mx // 2:
				mi *= 2
				c += 1
		if mx != mi:
			c += 1
		c += mx
		print(c)


T = int(input())
for z in range(T):
	(x, y) = sorted(map(int, input().split()))
	c = 0
	if x == 0 and y != 0 or (y == 0 and x != 0):
		print(-1)
	elif x == y:
		print(x)
	else:
		while x * 2 <= y:
			x = x * 2
			c = c + 1
		if x == y:
			print(c + y)
		else:
			print(c + y + 1)


import math

def findminimum(x, y):
	if x == y:
		return x
	if x == 0:
		return -1
	ans = 0
	while x < y:
		x *= 2
		ans += 1
	return ans + y
n = int(input())
while n > 0:
	(x, y) = list(map(int, input().split()))
	maxi = max(x, y)
	mini = min(x, y)
	print(findminimum(mini, maxi))
	n = n - 1


import math
for i in range(int(input())):
	(x, y) = map(int, input().split())
	if x == y:
		print(x)
		continue
	if x == 0 and y != 0:
		print('-1')
		continue
	if y == 0 and x != 0:
		print('-1')
		continue
	if x > y:
		(x, y) = (y, x)
	if int(math.log(y / x, 2)) == math.log(y / x, 2):
		sum = int(math.log(y / x, 2)) + y
	else:
		sum = int(math.log(y / x, 2)) + y + 1
	print(sum)


for _ in range(int(input())):
	(x, y) = list(map(int, input().split()))
	flag = 0
	ans = 0
	if x == 0 and y == 0:
		print(0)
		continue
	if x == 0 or y == 0:
		print(-1)
		continue
	if x == y:
		ans += y
		flag = 1
	else:
		flag = 1
		if y < x:
			(x, y) = (y, x)
		count = 0
		while x <= y:
			x *= 2
			count += 1
		count -= 1
		if x // 2 == y:
			ans = y + count
		else:
			ans = y + count + 1
	if flag == 0:
		print(-1)
	else:
		print(ans)


for _ in range(int(input())):
	(x, y) = map(int, input().split(' '))
	count = 0
	if x == y:
		print(x)
	elif x == 0 or y == 0:
		print('-1')
	elif x == 0 and y == 0:
		print(0)
	else:
		maximum = max(x, y)
		minimum = min(x, y)
		while minimum < maximum:
			minimum *= 2
			count += 1
		print(maximum + count)


t = int(input())
for _ in range(t):
	(x, y) = map(int, input().split())
	(x, y) = (min(x, y), max(x, y))
	if x == 0 and y == 0:
		print(0)
	elif x == 0 or y == 0:
		print(-1)
	else:
		ans = 0
		while x < y - x:
			x *= 2
			ans += 1
		diff = y - x
		ans += x - diff
		ans += min(1, diff)
		ans += 2 * diff
		print(ans)


from math import log2
t = int(input())
for _ in range(t):
	(x, y) = map(int, input().split())
	(x, y) = (min(x, y), max(x, y))
	if x == y:
		print(x)
	elif x == 0:
		print(-1)
	elif log2(y / x) == int(log2(y / x)):
		print(int(log2(y / x)) + y)
	else:
		ans = int(log2(y / x))
		x = x << int(log2(y / x))
		diff = y - x
		if diff == 1:
			print(ans + y + 1)
		else:
			print(ans + (x - diff + 1 + 2 * diff))


def po(test_rem):
	count = 0
	while test_rem > 1:
		test_rem //= 2
		count += 1
	return count
ans_list = []
noOfInputs = int(input())
for i in range(noOfInputs):
	(x, y) = input().split(' ')
	x = int(x)
	y = int(y)
	X = max(x, y)
	Y = min(x, y)
	if X == Y:
		ans_list.append(X)
	elif X == 0 or Y == 0:
		ans_list.append(-1)
	elif X == Y * 2 ** po(X // Y):
		ans_list.append(po(X // Y) + X)
	else:
		ans_list.append(po(X // Y) + X + 1)
for i in ans_list:
	print(i)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	count = max(x, y)
	mx = max(x, y)
	mn = min(x, y)
	if x == y:
		print(x)
	elif mn != 0:
		while mn < mx:
			mn *= 2
			count += 1
		print(count)
	else:
		print(-1)


for _ in range(int(input())):
	(x, y) = [int(x) for x in input().split()]
	mi = min(x, y)
	ma = max(x, y)
	if ma == mi:
		print(ma)
	else:
		ans = 0
		if mi != 0:
			while mi < ma:
				mi *= 2
				ans += 1
			print(ans + ma)
		else:
			print(-1)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	if x * y == 0 and x + y != 0:
		print(-1)
	else:
		ans = 0
		a = min(x, y)
		b = max(x, y)
		while a < b:
			a *= 2
			ans += 1
		print(ans + b)


from operator import itemgetter
from sys import maxsize, stdin
from collections import Counter, defaultdict
t = int(stdin.readline().strip())
while t > 0:
	(x, y) = map(int, stdin.readline().strip().split(' '))
	res = 0
	if x > y:
		(x, y) = (y, x)
	if x == 0 and y == 0:
		print(0)
	elif x == 0 and y != 0:
		print(-1)
	elif x != 0 and y != 0:
		while x < y:
			res += 1
			x *= 2
		print(res + y)
	t -= 1


noOfInput = int(input())
i = 0
while i < noOfInput:
	(x, y) = input().split(' ')
	(x, y) = (int(x), int(y))
	if x > y:
		(x, y) = (y, x)
	if x == 0 and y == 0:
		print(0)
	elif x == y:
		print(x)
	elif x == 0:
		print(-1)
	else:
		result = 0
		orgxy = y
		while x < y:
			x = 2 * x
			result += 1
		res = result + y
		print(res)
	i += 1


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	ans = 0
	if a > b:
		(a, b) = (b, a)
	if a == 0 and b == 0:
		print(0)
	elif a == 0:
		print(int(-1))
	else:
		while a < b:
			a *= 2
			ans += 1
		print(ans + b)


t = int(input())
for _ in range(t):
	(x, y) = map(int, input().split())
	if x > y:
		(x, y) = (y, x)
	if x == y:
		print(x)
	elif x == 0 or y == 0:
		print(-1)
	else:
		steps = 0
		while x < y:
			x *= 2
			steps += 1
		steps += y
		print(steps)


import math

def solve(x, y):
	(x, y) = (max(x, y), min(x, y))
	if x == y:
		print(x)
	elif y == 0 and x == 0:
		print(0)
	elif y == 0:
		print(-1)
	else:
		i = int(math.log(x / y, 2))
		y = 2 ** i * y
		if x == y:
			print(y + i)
		else:
			k = 2 * y - x
			steps = x + 1 + i
			print(steps)
t = int(input())
for _ in range(t):
	(x, y) = list(map(int, input().split()))
	solve(x, y)


import math

def solve(x, y):
	(x, y) = (max(x, y), min(x, y))
	if x == y:
		print(x)
	elif y == 0 and x == 0:
		print(0)
	elif y == 0 and x != 0:
		print(-1)
	else:
		ans = 0
		while y < x:
			y = 2 * y
			ans += 1
		ans += x
		print(ans)
t = int(input())
for _ in range(t):
	(x, y) = list(map(int, input().split()))
	solve(x, y)


t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	m = 0
	if a >= b:
		x = b
		y = a
	else:
		x = a
		y = b
	if x == y:
		print(x)
	elif x == 0 and y != 0:
		print(-1)
	else:
		while x < y:
			x *= 2
			m += 1
		if x == y:
			m += y
			print(m)
		else:
			m = m + (x - (y - x))
			m = m + 2 * (y - x)
			print(m)


import math
t = int(input())
for _ in range(t):
	(x, y) = map(int, input().split())
	if x < y:
		(y, x) = (x, y)
	if x == 0 and y == 0:
		print(0)
	elif x == 0 or y == 0:
		print(-1)
	elif x == y:
		print(y)
	else:
		a = math.log2(x / y)
		if int(a) == a:
			c = int(a)
		else:
			c = int(a) + 1
		print(c + x)


for x in range(int(input())):
	(a, b) = map(int, input().split())
	(a, b) = (min(a, b), max(a, b))
	if a == b:
		print(a)
		continue
	elif a == 0:
		print(-1)
		continue
	else:
		count = 1
		while 2 * a < b:
			a *= 2
			count += 1
		count += b
		print(count)
		continue


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	c = 0
	if x == 0 and y == 0:
		print(0)
	elif x == 0 and y != 0:
		print(-1)
	elif y == 0 and x != 0:
		print(-1)
	else:
		if y > x:
			(x, y) = (y, x)
		c += x
		while y < x:
			c += 1
			y <<= 1
		print(c)


from math import ceil, log
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	if a > b:
		(a, b) = (b, a)
	if a == 0 and b == 0:
		print(0)
	elif a == 0 or b == 0:
		print(-1)
	else:
		k = ceil(log(b / a, 2))
		print(k + b)


from math import ceil, log
test = int(input())
while test:
	(a, b) = map(int, input().split())
	if a > b:
		(a, b) = (b, a)
	if a == 0 and b == 0:
		print(0)
	elif a == 0 or b == 0:
		print(-1)
	else:
		k = ceil(log(b / a, 2))
		print(k + b)
	test -= 1


def so(x, y):
	if x > y:
		(x, y) = (y, x)
	if x == 0 and y == 0:
		print(0)
		return
	elif x == 0 and y > 0:
		print(-1)
	else:
		count = 0
		while x < y:
			x *= 2
			count += 1
		print(count + y)

def solve():
	[x, y] = list(map(int, input().split()))
	re = so(x, y)
n = int(input())
for i in range(n):
	solve()


t = int(input())
for T in range(t):
	(x, y) = map(int, input().split())
	if x > y:
		c = x
		x = y
		y = c
	if x == 0 and y == 0:
		print(0)
	elif x == 0 or y == 0:
		print(-1)
	else:
		ans = 0
		while 2 * x < y:
			x = 2 * x
			ans += 1
		ans += 2 * x - y
		x = y - x
		y = 2 * x
		if x != 0:
			ans += 1
		ans += y
		print(ans)


t = int(input())
while t:
	(a, b) = map(int, input().split(' '))
	if a > b:
		(a, b) = (b, a)
	if a == 0 and b == 0:
		print(0)
	elif a == 0 or b == 0:
		print(-1)
	else:
		count = 0
		while a < b:
			a *= 2
			count += 1
		if a > b:
			count -= 1
			a //= 2
		diff = abs(b - a)
		count += min(a, b) - diff
		if diff > 0:
			count += 1
			count += 2 * diff
		print(count)
	t -= 1


t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	if x == y:
		print(x)
	elif x == 0 or y == 0:
		print(-1)
	else:
		a = min(x, y)
		b = max(x, y)
		c = 0
		while a * 2 < b:
			a = a * 2
			c += 1
		d = b - a
		c = c + (a - d)
		a = d * 2
		c += 1
		c += a
		print(c)


test_cases = int(input())
for i in range(test_cases):
	(X, Y) = map(int, input().split())
	count = 0
	smaller = min(X, Y)
	greater = max(X, Y)
	if X == 0 and Y == 0:
		print(X)
	elif smaller == 0:
		print(-1)
	else:
		while greater > smaller:
			smaller = smaller * 2
			count += 1
		print(count + greater)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	MAX = max(x, y)
	MIN = min(x, y)
	if x == 0 and y == 0:
		print(0)
	elif MIN == 0:
		print(-1)
	else:
		c = 0
		while MIN < MAX:
			MIN *= 2
			c += 1
		print(c + MAX)


from math import *

def solve(a, b):
	if a > b:
		return solve(b, a)
	elif a == b:
		return a
	if a == 0:
		return -1
	ans = 0
	while 2 * a <= b:
		a *= 2
		ans += 1
	d = b - a
	if d:
		ans += a - d + 1
		b -= a - d
	return ans + b
t = int(input())
for x in range(t):
	(a, b) = map(int, input().split(' '))
	print(solve(a, b))


T = int(input())
for tc in range(T):
	(X, Y) = map(int, input().split())
	x = max(X, Y)
	y = min(X, Y)
	res = 0
	if x == 0 and y == 0:
		print(0)
		continue
	if x == 0 or y == 0:
		print(-1)
		continue
	if x == y:
		print(x)
		continue
	while y < x:
		y = y * 2
		res += 1
	if y > x:
		y = y // 2
		res -= 1
	diff = abs(x - y)
	if diff == 0:
		res += x
		print(res)
		continue
	diff = y - diff
	res += diff
	Y = y - diff
	X = x - diff
	res += 1
	res += X
	print(res)


T = int(input())
for tc in range(T):
	(a, b) = map(int, input().split(' '))
	x = min(a, b)
	y = max(a, b)
	if x == 0 and y == 0:
		print(0)
		continue
	if x == 0 or y == 0:
		print(-1)
		continue
	res = 0
	while x < y:
		x = x << 1
		res += 1
	print(res + y)


def func(_a, _b):
	ret = 0
	a = _a if _a < _b else _b
	b = _b if _b > _a else _a
	if a == 0 and b == 0:
		return 0
	elif a == 0 and b != 0:
		return -1
	while a > 0 and b > 0:
		if 2 * a <= b:
			a = 2 * a
			ret = ret + 1
		else:
			ret = ret + (a - (b - a))
			a = b - a
			b = 2 * a
	return ret
case_num = int(input())
for t in range(0, case_num):
	s = input()
	arr = s.split(' ')
	a = int(arr[0])
	b = int(arr[1])
	print(func(a, b))


(yes, no) = ('yes', 'no')
tc = int(input())
for case in range(tc):
	(x, y) = map(int, input().split())
	if (x == 0) ^ (y == 0):
		print(-1)
	else:
		(x, y) = (min(x, y), max(x, y))
		cnt = 0
		while x < y:
			x *= 2
			cnt += 1
		print(y + cnt)


t = int(input())
while t:
	(x, y) = map(int, input().split())
	count = 0
	if x == y:
		print(x)
	elif x == 0 or y == 0:
		print(-1)
	else:
		(minn, maxx) = (min(x, y), max(x, y))
		ans = 0
		while minn < maxx:
			minn *= 2
			ans += 1
		if minn >= maxx:
			minn //= 2
			ans -= 1
		temp = minn - (maxx - minn)
		minn -= temp
		maxx -= temp
		ans += temp + 1 + maxx
		print(ans)
	t = t - 1


import math
t = int(input())
for it in range(t):
	(x, y) = (int(i) for i in input().split())
	if x > y:
		(x, y) = (y, x)
	if y == 0:
		print(0)
	elif x == 0:
		print(-1)
	elif x == y:
		print(x)
		continue
	else:
		ans = 0
		temp = 1
		while 2 * temp * x < y:
			ans += 1
			temp *= 2
		print(ans + y + 1)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	if x == y:
		print(x)
	elif x == 0 or y == 0:
		print(-1)
	else:
		(minn, maxx) = (min(x, y), max(x, y))
		ans = 0
		while minn < maxx:
			minn *= 2
			ans += 1
		if minn >= maxx:
			minn //= 2
			ans -= 1
		temp = minn - (maxx - minn)
		minn -= temp
		maxx -= temp
		ans += temp + 1 + maxx
		print(ans)


from math import log2
for i in range(int(input())):
	(A, B) = map(int, input().split())
	a = max(A, B)
	b = A + B - a
	if b != 0:
		c = int(log2(a / b))
		d = b
		for j in range(c):
			d *= 2
		if d != a:
			c += 1
		print(c + a)
	elif a == 0 and b == 0:
		print('0')
	else:
		print('-1')


for i in range(int(input())):
	(x, y) = map(int, input().split())
	if x == y:
		print(y)
	elif x == 0 or y == 0:
		print(-1)
	else:
		if x > y:
			(x, y) = (y, x)
		c = 0
		while x < y:
			x *= 2
			c += 1
		if x >= y:
			x //= 2
			c -= 1
		d = 2 * x - y
		x -= d
		y -= d
		x *= 2
		c += 1
		c += y
		c += d
		print(c)


import math
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	a = min(x, y)
	b = max(x, y)
	c = 0
	ans = 0
	if x == y:
		print(x)
		continue
	if x == 0 or y == 0:
		print(-1)
		continue
	while True:
		a = a * 2
		c += 1
		if a >= b:
			a = a // 2
			c -= 1
			break
	ans += c
	c = a - (b - a)
	a -= c
	b -= c
	ans += c
	ans += 1
	c = b
	ans += c
	print(ans)


from math import sqrt
from math import ceil
from math import log2
try:
	for k in range(int(input())):
		(A, B) = map(int, input().split())
		w = max(A, B)
		x = A + B - w
		if x != 0:
			c = int(log2(w / x))
			a = x
			for i in range(0, c):
				a = a * 2
			if a != w:
				c = c + 1
				print(c + w)
			else:
				print(c + w)
		elif w == 0 and x == 0:
			print('0')
		else:
			print('-1')
except:
	pass


t = int(input())
for _ in range(t):
	(X, Y) = map(int, input().split())
	if X == Y:
		print(X)
	elif X == 0 or Y == 0:
		print(-1)
	else:
		temp_min = min(X, Y)
		temp_max = max(X, Y)
		op = 0
		while temp_min < temp_max:
			temp_min *= 2
			op += 1
		if temp_min >= temp_max:
			temp_min = temp_min // 2
			op -= 1
		temp = temp_min - (temp_max - temp_min)
		temp_min -= temp
		temp_max -= temp
		op += temp
		temp_min *= 2
		op += 1
		op += temp_max
		print(op)