Read problems statements in [Mandarin Chinese], [Russian], [Vietnamese] and [Bengali] as well.

You have taken an eating challenge from Chef and now you have to eat exactly $Y$ burgers. You will eat in the following way:

In the first minute you will eat exactly $X$ burgers and every minute after that you will eat exactly twice the number of burgers you ate in the previous minute. 
Since you can get tired of eating, Chef also allows you take a break from eating for exactly $1$ minute.
When you start eating again after taking a break, your eating streak resets, i.e. in the first minute after the break you will eat exactly $X$ burgers and every minute after that you will eat exactly double the burgers you ate on the previous minute. 

Let $a_{1}, a_{2}, ..., a_{k}$ be the lengths of your eating streaks in minutes. Chef requires that all $a_{i}$ are pairwise distinct.

Find the minimum number of minutes you need to eat exactly $Y$ burgers or determine it is impossible to do so.

------ Input ------

The first line 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 $X$ and $Y$.

------ Output ------
For each test case, print a single line containing one integer — the minimum number of minutes you need to eat exactly $Y$ burgers, or $−1$ if it is impossible.

------ Constraints  ------
$1≤ T≤ 10^{5}$
$1≤ X,Y≤ 10^{18}$

----- Sample Input 1 ------ 
2

1 7

1 4
----- Sample Output 1 ------ 
3

4

Difficulty: HARD
Tags: Bit manipulation

Constructive algorithms

Greedy algorithms

Number theory

Mathematics

Ad-hoc
Skill types: Bit manipulation

Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	temp = []
	m = 1
	while m * x <= y:
		temp.append(m * x)
		m = 2 * m + 1
	count = 0
	for i in range(len(temp) - 1, -1, -1):
		if temp[i] <= y:
			y -= temp[i]
			count += i + 2
	count -= 1
	if y != 0:
		print(-1)
	else:
		print(count)


from bisect import *
import sys
input = sys.stdin.readline

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

def lis():
	return list(map(int, input().split()))

def ma():
	return map(int, input().split())
t = inp()
while t:
	t -= 1
	(x, y) = ma()
	if x == y:
		print(1)
		continue
	fl = 0
	mo = 1000000
	have = []
	for i in range(1, 61):
		have.append([x * (2 ** i - 1), i])
	have.sort(reverse=True)
	cur = 0
	mo = 0
	for i in have:
		if i[0] <= y:
			y -= i[0]
			mo += i[1] + 1
		if y == 0:
			mo -= 1
			fl = 1
			break
	if fl == 0:
		mo = -1
	print(mo)


li = [2 ** i - 1 for i in range(1, 61)]

def sure(m):
	seen = []
	i = 60
	for it in li[-1::-1]:
		if it <= m:
			m -= it
			seen.append(i)
		if m == 0:
			break
		i -= 1
	if m != 0:
		return (False, [])
	return (True, seen)

def func(x, y):
	if y % x:
		return -1
	d = y // x
	(st, li) = sure(d)
	if not st:
		return -1
	ans = sum(li) + len(li) - 1
	return ans
t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	print(func(x, y))


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	l = []
	if y % x != 0:
		print(-1)
	else:
		m = 1
		y = y // x
		while y >= 2 ** m - 1:
			z = 2 ** m - 1
			l.append(z)
			m += 1
		s = 0
		for i in range(len(l) - 1, -1, -1):
			if l[i] <= y:
				y -= l[i]
				s += i + 2
		s -= 1
		if y != 0:
			print(-1)
		else:
			print(s)


import sys
t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	if y % x != 0:
		print(-1)
		continue
	a = y // x + 1
	if a % 2 == 1:
		a += 1
		j = 2
	else:
		j = 1
	b = '{0:0b}'.format(a)
	ans = sys.maxsize
	while j <= len(b):
		if b.count('1') == j:
			d = j - 1
			ind = b.index('1')
			while ind != -1:
				d += len(b) - ind - 1
				try:
					ind = b.index('1', ind + 1)
				except ValueError:
					break
			if d < ans:
				ans = d
		j += 2
		a += 2
		b = '{0:0b}'.format(a)
	if ans != sys.maxsize:
		print(ans)
	else:
		print(-1)


from collections import defaultdict, Counter
from math import sqrt, log10, log2, log, gcd, ceil, floor
from bisect import bisect_left, bisect_right
from itertools import permutations
import sys, io, os
input = sys.stdin.readline
sys.setrecursionlimit(10000)

def get_list():
	return [int(i) for i in input().split()]
inf = float('inf')
t = 1
arr = [pow(2, i) - 1 for i in range(1, 66)]
for i in range(int(input())):
	(x, y) = get_list()
	if y % x != 0:
		print(-1)
		continue
	arr1 = [x * j for j in arr]
	dict = defaultdict(int)
	pos = 1
	counter = 0
	while y:
		index = bisect_right(arr1, y) - 1
		if dict[index] == 1:
			pos = 0
			break
		dict[index] = 1
		y -= arr1[index]
		counter += index + 1
		counter += 1
	if pos:
		counter -= 1
		print(counter)
	else:
		print(-1)


from collections import defaultdict
import math as m
t = int(input())
for k in range(t):
	(x, y) = map(int, input().split())
	ans = -1
	if y % x != 0:
		print(-1)
	else:
		for i in range(61, 0, -1):
			if x * (2 ** i - 1) <= y:
				y = y - x * (2 ** i - 1)
				ans += 1
				ans += i
		if y == 0:
			print(ans)
		else:
			print(-1)


for t in range(int(input())):
	(x, y) = map(int, input().split())
	if y % x:
		print(-1)
		continue
	y //= x
	flag = False
	ans = float('inf')
	(low, high) = (1, 65)
	for i in range(1, 65):
		tt = y + i
		binary = bin(tt)[2:]
		if binary.count('1') == i:
			binary = binary[::-1]
			si = 0
			for j in range(len(binary)):
				if binary[j] == '1':
					si += j
			si = si + i - 1
			ans = si
			flag = True
			break
	if flag:
		print(ans)
	else:
		print(-1)


import sys
import math
T = int(input())
for test_case in range(T):
	(x, y) = map(int, sys.stdin.readline().strip().split())
	upto = int(math.log2(y / x + 1))
	dp = [(2 ** i - 1) * x for i in range(upto, 0, -1)]
	i = 0
	j = upto
	ans = 0
	b = True
	while i < upto and y != 0:
		if y >= dp[i]:
			y -= dp[i]
			if b:
				ans += j
				b = False
			else:
				ans += j + 1
		i += 1
		j -= 1
	if y == 0:
		print(ans)
	else:
		print(-1)


import sys
import math
import bisect
from math import log2

def input():
	return sys.stdin.readline().strip()

def iinput():
	return int(input())

def rinput():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))
mod = int(1000000000.0) + 7
for _ in range(iinput()):
	(x, y) = rinput()
	nmax = int(log2(y / x + 1))
	t = [(2 ** i - 1) * x for i in range(nmax, 0, -1)]
	n = len(t)
	i = 0
	j = nmax
	ans = 0
	b = True
	while i < n and y != 0:
		if y >= t[i]:
			y -= t[i]
			if b:
				ans += j
				b = False
			else:
				ans += j + 1
		i += 1
		j -= 1
	if y == 0:
		print(ans)
	else:
		print(-1)


t = int(input())
for _ in range(t):
	(x, y) = map(int, input().split())
	ans = 0
	if y % x != 0:
		print(-1)
	else:
		y //= x
		for i in range(61, 0, -1):
			if y >= (1 << i) - 1:
				ans += i + 1
				y -= (1 << i) - 1
		print([-1, ans - 1][y == 0])


import time
try:
	t = int(input())
	p = 10 ** 9 + 7
	while t:
		t -= 1
		(x, y) = map(int, input().split())
		start = time.time()
		if y % x == 0:
			y = y // x
			flag = 1
			for n in range(1, 60):
				b = y + n
				cnt = 0
				j = 0
				minutes = 0
				if b & 1:
					continue
				m = bin(b)[2:]
				cnt = m.count('1')
				if cnt == n:
					flag = 0
					lm = len(m)
					for i in range(lm):
						if m[lm - 1 - i] == '1':
							minutes += i
					print(n + minutes - 1)
					break
			if flag == 1:
				print(-1)
		else:
			print(-1)
	end = time.time()
except:
	pass


from collections import deque, defaultdict
from math import sqrt, ceil, factorial, floor, inf, log2, sqrt, gcd
import bisect
import copy
from itertools import combinations
import sys

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()
from collections import defaultdict

def func(y, x):
	if y % x != 0:
		return inf
	else:
		y = y // x
		(ans, k) = (0, 0)
		for i in range(len(arr) - 1, -1, -1):
			if arr[i] <= y:
				ans += i + 1
				k += 1
				y -= arr[i]
		if y == 0:
			return ans + k - 1
		else:
			return inf
arr = []
for i in range(1, 62):
	arr.append(2 ** i - 1)
for _ in range(int(input())):
	(x, y) = get_ints()
	mini = inf
	mini = min(mini, func(y, x))
	if mini == inf:
		print(-1)
	else:
		print(mini)


import math
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	if y % x != 0:
		print(-1)
	else:
		arr = []
		y = y // x
		p = 1
		c = 0
		k = 0
		for i in range(1, 62):
			arr.append(2 ** i - 1)
		for i in range(len(arr) - 1, -1, -1):
			if arr[i] <= y:
				c += i + 1
				k += 1
				y -= arr[i]
		if y == 0:
			print(c + k - 1)
		else:
			print(-1)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	if y % x != 0:
		print(-1)
	else:
		arr = []
		y = y // x
		p = 1
		c = -1
		for i in range(1, 61):
			arr.append(2 ** i - 1)
		for i in range(len(arr) - 1, -1, -1):
			if arr[i] <= y:
				c += i + 2
				y -= arr[i]
		if y == 0:
			print(c)
		else:
			print(-1)


def f(n):
	(c, l) = (-1, len(bin(n)) - 2)
	while l != 0 and n != 0:
		t = int('1' * l, 2)
		if t <= n:
			n -= t
			c += l + 1
		l -= 1
	if not n:
		return c
	else:
		return -1
T = int(input())
for n1 in range(T):
	(x, y) = [int(i) for i in input().split(' ')]
	if y % x == 0:
		print(f(y // x))
	else:
		print(-1)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	if y % x != 0:
		print(-1)
	else:
		ans = 0
		l = []
		for i in range(1, 61):
			l.append(2 ** i - 1)
		for i in range(len(l) - 1, -1, -1):
			if y - l[i] * x >= 0:
				y -= l[i] * x
				ans += i + 1
				if y > 0:
					ans += 1
		if y == 0:
			print(ans)
		else:
			print(-1)


def good(x, y):
	if x > y or y % x != 0:
		return -1
	lo = 0
	hi = 60
	ans = -1
	while lo <= hi:
		mid = (lo + hi) // 2
		a = (2 ** mid - 1) * x
		if y >= a:
			ans = mid
			lo = mid + 1
		else:
			hi = mid - 1
	arr = []
	count = 0
	for i in range(1, ans + 1):
		arr.append((2 ** i - 1) * x)
	for i in range(ans - 1, -1, -1):
		if arr[i] <= y:
			count += i + 2
			y -= arr[i]
	count -= 1
	if y != 0:
		return -1
	else:
		return count
t = int(input())
for l in range(t):
	(x, y) = map(int, input().split())
	print(good(x, y))


T = int(input())
for i in range(T):
	(X, Y) = [int(x) for x in input().split()]
	if Y % X != 0:
		print(-1)
	else:
		ans = 0
		Y = Y // X
		s = set()
		while True:
			c = bin(Y)
			c = str(c)
			c = c[2:]
			if Y == 0:
				print(ans)
				break
			elif Y == (1 << len(c)) - 1:
				ans += len(c)
				if len(c) in s:
					print(-1)
				else:
					print(ans)
				break
			else:
				Y -= (1 << len(c) - 1) - 1
				if len(c) - 1 in s:
					print(-1)
					break
				s.add(len(c) - 1)
				ans += len(c)


from collections import Counter, defaultdict
import math, bisect
arr = [0, 1]
mp = defaultdict(int)
mp[1] = 1
for i in range(2, 61):
	val = arr[-1] * 2 + 1
	arr.append(val)
	mp[val] = 1
for _ in range(int(input())):
	(x, y) = list(map(int, input().split()))
	if y % x != 0:
		print(-1)
		continue
	y //= x
	x = 1
	cnt = 0
	res = 0
	flag = []
	while y != 0:
		cnt += 1
		if mp[y] == 1:
			n = arr.index(y)
		else:
			n = bisect.bisect_left(arr, y) - 1
		flag.append(n)
		y -= 2 ** n - 1
		res += n
	if len(flag) != len(list(set(flag))):
		print(-1)
	else:
		print(res + cnt - 1)


from math import *
for i in range(int(input())):
	(x, y) = map(int, input().split())
	if y % x != 0:
		print(-1)
	else:
		y = y // x
		ans = 0
		for len in range(61, 0, -1):
			a = (1 << len) - 1
			if a <= y:
				y -= a
				ans = ans + len + 1
		if y == 0:
			print(ans - 1)
		else:
			print(-1)


def ans(x, y):
	if y % x != 0:
		return -1
	y //= x
	ans = 0
	for i in range(59, -1, -1):
		if y >= burgers[i]:
			ans += days[i]
			y -= burgers[i]
		if y == 0:
			return ans - 1
	return -1
days = [2]
burgers = [1]
while len(burgers) < 60:
	days.append(days[-1] + 1)
	burgers.append(burgers[-1] * 2 + 1)
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	print(ans(x, y))


import sys
input = sys.stdin.readline
import math
dp = [1] * 63
x = 2
for i in range(1, 63):
	dp[i] = dp[i - 1] + x
	x = x * 2
t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	if y % x != 0:
		print(-1)
		continue
	y = y // x
	p = 62
	ans = []
	while p >= 0:
		if dp[p] <= y:
			y = y - dp[p]
			ans.append(p + 1)
		p = p - 1
	if y != 0:
		print(-1)
		continue
	print(sum(ans) + len(ans) - 1)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	if y % x != 0:
		print(-1)
	else:
		y = y // x
		flag = 1
		for i in range(1, 60):
			n = bin(y + i)[2:]
			if n.count('1') == i:
				n = n[::-1]
				s = 0
				for j in range(len(n)):
					if n[j] == '1':
						s += j
				s = s + i - 1
				print(s)
				flag = 0
				break
		if flag:
			print(-1)


for _ in range(int(input())):
	(x, y) = [int(x) for x in input().split()]
	if y % x != 0:
		print(-1)
	else:
		ans = 0
		options = [2 ** i - 1 for i in range(1, 64)]
		ab = y // x
		for i in range(len(options) - 1, -1, -1):
			if ab - options[i] >= 0:
				ab -= options[i]
				ans += i + 1
				if ab > 0:
					ans += 1
		if ab == 0:
			print(ans)
		else:
			print(-1)


from sys import stdin, stdout
from math import ceil, floor, sqrt, log, log2, log10
from collections import Counter
from typing import ByteString
input = stdin.readline
t = int(input())

def solve():
	pass
for _ in range(t):
	(x, y) = map(int, input().split())
	if y % x != 0:
		print(-1)
		continue
	total = 0
	curr = 0
	a = x
	for i in range(60, -1, -1):
		if x * (2 ** (i + 1) - 1) <= y:
			total += 1
			y -= x * (2 ** (i + 1) - 1)
			total += i + 1
	print(total - 1 if not y else -1)


t = int(input())
for _ in range(t):
	(x, y) = map(int, input().split())
	if y % x != 0:
		print(-1)
		continue
	y = y // x
	cnt = 0
	for i in range(60, 0, -1):
		ele = 2 ** i - 1
		if ele <= y:
			y -= ele
			cnt += i + 1
			if y == 0:
				break
	if y != 0:
		print(-1)
	else:
		print(cnt - 1)


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log2, ceil
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from bisect import insort
from collections import Counter
from collections import deque
from heapq import heappush, heappop, heapify
from itertools import permutations, combinations
from itertools import accumulate as ac
from random import randint as ri
mod = int(1000000000.0) + 7
ip = lambda : int(stdin.readline())
inp = lambda : map(int, stdin.readline().split())
ips = lambda : stdin.readline().rstrip()
out = lambda x: stdout.write(str(x) + '\n')
t = ip()
for _ in range(t):
	(x, y) = inp()
	if y % x == 0:
		y = y // x
		nn = 5
		bit = [0] * nn
		cur = y
		ans = 0
		last = None
		val = []
		while cur > 0:
			mm = len(bin(cur)[2:])
			if pow(2, mm) - 1 == cur:
				ans += mm
				last = cur
				cur -= pow(2, mm) - 1
				val.append(mm)
			else:
				last = cur
				cur -= pow(2, mm - 1) - 1
				ans += mm - 1
				ans += 1
				val.append(mm - 1)
		if len(set(val)) == len(val):
			pass
		else:
			ans = -1
	else:
		ans = -1
	print(ans)


from sys import stdin, stdout
stdin.readline

def mp():
	return list(map(int, stdin.readline().strip().split()))

def it():
	return int(stdin.readline().strip())
from collections import defaultdict as dd, Counter as C, deque
from math import ceil, gcd, sqrt, factorial, log2, floor
from bisect import bisect_right as br, bisect_left as bl
for _ in range(it()):
	(x, n) = mp()
	if n % x:
		print(-1)
		continue
	n //= x
	v = []
	for i in range(60):
		v.append(1 << i)
	for i in range(1, 60):
		v[i] += v[i - 1]
	s = set(v)
	v.reverse()
	ans = 0
	for i in v:
		if n >= i:
			ans += len(bin(i)) - 2
			n -= i
			if n != 0:
				ans += 1
	if n != 0:
		print(-1)
	else:
		print(ans)


t = int(input())
for _ in range(t):
	(x, y) = map(int, input().split())
	alpha = []
	m = 1
	while m * x <= y:
		alpha.append(m * x)
		m = 2 * m + 1
	cnt = 0
	for i in range(len(alpha) - 1, -1, -1):
		if alpha[i] <= y:
			y -= alpha[i]
			cnt += i + 2
	cnt -= 1
	if y != 0:
		print(-1)
	else:
		print(cnt)


from collections import defaultdict
import sys
for _ in range(int(input())):
	(n, y) = map(int, sys.stdin.readline().split())
	if y % n != 0:
		print(-1)
	else:
		target = y // n
		ans = 0
		s = 0
		i = 1
		f = 0
		c = 0
		for i in range(60, 0, -1):
			v = (1 << i) - 1
			if v > target - s:
				continue
			elif f == 0:
				s += v
				ans += i
				f = 1
			else:
				s += v
				ans += i
				c += 1
		if s == target:
			sys.stdout.write(str(ans + c) + '\n')
		else:
			sys.stdout.write(str(-1) + '\n')


from collections import defaultdict
for _ in range(int(input())):
	(n, y) = map(int, input().split())
	if y % n != 0:
		print(-1)
	else:
		target = y // n
		ans = 0
		s = 0
		i = 1
		f = 0
		c = 0
		for i in range(60, 0, -1):
			v = (1 << i) - 1
			if v > target - s:
				continue
			elif f == 0:
				s += v
				ans += i
				f = 1
			else:
				s += v
				ans += i
				c += 1
		if s == target:
			print(ans + c)
		else:
			print(-1)


def burg(n):
	o = None
	c = 0
	r = 0
	while n:
		b = bin(n)[2:]
		l = len(b)
		if not '0' in b:
			if o == n:
				return -1
			c += l
			r += 1
			break
		else:
			o = 2 ** (l - 1) - 1
			c += l - 1
			r += 1
			n -= o
	return c + r - 1
for _ in range(int(input())):
	(X, Y) = map(int, input().split())
	print(burg(Y // X)) if Y % X == 0 else print(-1)


import math

def foo(n, r):
	return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
mod = pow(10, 9) + 7
from collections import defaultdict
t = int(input())
pre = []
limit = pow(10, 18) + 10
p = 1
while p < limit:
	pre.append(p)
	p *= 2
for i in range(1, len(pre)):
	pre[i] += pre[i - 1]
for t1 in range(0, t):
	(x, k) = map(int, input().split())
	time = 0
	flag = 0
	time = 0
	ans = 0
	a = defaultdict(int)
	for i in range(len(pre) - 1, -1, -1):
		while x * pre[i] <= k:
			k -= x * pre[i]
			time += i + 1
			a[i + 1] += 1
	if k != 0:
		ans = -1
	else:
		for i in a.items():
			if i[1] > 1:
				ans = -1
		if ans != -1:
			ans += time
			ans += len(a) - 1
	print(ans)


import sys
from bisect import bisect_right as rb
from collections import deque
from queue import PriorityQueue
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
inv = lambda x: pow(x, mod - 2, mod)
mod = 10 ** 9 + 7
dp = [1 for i in range(64)]
for i in range(1, 64):
	dp[i] = dp[i - 1] * 2
for _ in range(ii()):
	(x, y) = il()
	if y % x:
		print(-1)
		continue
	y = y // x
	ans = 0
	c = 0
	for i in range(63, 0, -1):
		if dp[i] - 1 <= y:
			ans += i
			y -= dp[i] - 1
			c += 1
	if y == 0:
		print(ans + c - 1)
	else:
		print(-1)


from bisect import bisect_left
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	if y % x != 0:
		print(-1)
	else:
		ans = 0
		l = []
		for i in range(1, 61):
			l.append(2 ** i - 1)
		for i in range(len(l) - 1, -1, -1):
			if y - l[i] * x >= 0:
				y -= l[i] * x
				ans += i + 1
				if y > 0:
					ans += 1
		if y == 0:
			print(ans)
		else:
			print(-1)


def answer():
	if y % x:
		return -1
	d = y // x
	value = []
	for i in range(61):
		value.append([(1 << i) - 1, i])
	(b, ans) = (-1, 0)
	for i in range(60, 0, -1):
		if value[i][0] <= d:
			d -= value[i][0]
			ans += value[i][1]
			b += 1
	if d:
		return -1
	return ans + b
for T in range(int(input())):
	(x, y) = map(int, input().split())
	print(answer())


for _ in range(int(input())):
	(x, y) = map(int, input().split(' '))
	if y % x != 0:
		print(-1)
	else:
		ans = 10 ** 18
		a = y // x
		for k in range(1, 61):
			num = a + k
			s = bin(num).replace('0b', '')
			f = s[:-1].count('1')
			n = len(s)
			if f == k and s[-1] != '1':
				res = f - 1
				for i in range(len(s)):
					if s[i] == '1':
						res = res + (n - i - 1)
				ans = min(ans, res)
				break
		if ans == 10 ** 18:
			ans = -1
		print(ans)


mxV = (1 << 60) - 1
for t in range(int(input())):
	(x, y) = tuple(map(int, input().strip().split()))
	ans = -1
	t = 60
	v = mxV
	if y % x == 0:
		ans = 0
		y = y // x
		b = -1
		while y > 0 and v > 0:
			while v > y:
				v >>= 1
				t -= 1
			y -= v
			ans += t
			v >>= 1
			t -= 1
			b += 1
		if y > 0:
			ans = -1
		else:
			ans += b
	print(ans)


import numpy as np
m = {}
power = [1] * 60
m[1] = 1
for i in range(1, 60):
	power[i] = 2 * power[i - 1] + 1
	m[power[i]] = i + 1
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	if y % x != 0:
		print(-1)
	else:
		p = y // x
		c = 0
		i = 59
		t = -1
		k = 0
		while i >= 0 and p > 0:
			if power[i] <= p:
				c += m[power[i]] + k
				p -= power[i]
				k = 1
			i -= 1
		if p != 0:
			c = -1
		print(c)


import sys
import os.path
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
depth = 1000005
mod = 1000000007
sys.setrecursionlimit(depth)
from collections import defaultdict
nums = [0 for _ in range(70)]
for i in range(1, 70):
	nums[i] = 2 * nums[i - 1] + 1

def fun(n):
	(hi, lo, ans) = (69, 1, 1)
	while hi >= lo:
		mid = (hi + lo) // 2
		if nums[mid] <= n:
			ans = max(ans, mid)
			lo = mid + 1
		else:
			hi = mid - 1
	n = n - nums[ans]
	return (n, ans)
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	if y % x != 0:
		print(-1)
		continue
	ans = 0
	z = y // x
	s = set()
	while z > 0:
		(z, c) = fun(z)
		if c in s:
			ans = -1
			break
		else:
			s.add(c)
		ans += c
		if z > 0:
			ans += 1
	print(ans)


from bisect import bisect_left
ck = []
for i in range(1, 61):
	ck.append(2 ** i - 1)
for _ in range(int(input())):
	(y, x) = map(int, input().split())
	if x % y:
		print(-1)
	else:
		x = x // y
		ans = 0
		last = -1
		bol = True
		while x:
			t = bisect_left(ck, x)
			if ck[t] > x:
				t -= 1
			ans += t + 1
			x -= ck[t]
			if x:
				ans += 1
			if last == t:
				bol = False
				break
			last = t
		if not bol:
			print(-1)
		else:
			print(ans)


t = int(input())
for _ in range(t):
	(x, y) = map(int, input().split())
	total = x
	arr = [0, x]
	while total < y:
		x *= 2
		arr.append(x)
		total += arr[-1]
	n = len(arr)
	for i in range(1, n):
		arr[i] = arr[i] + arr[i - 1]
	arr = arr[::-1]
	count = -1
	for x in arr:
		if y >= x:
			y -= x
			count += n
		n -= 1
		if y <= 0:
			break
	if y == 0:
		print(count)
	else:
		print(-1)


import math
from collections import defaultdict
DEBUG = True

def log(*args, **kwargs):
	if DEBUG:
		print(*args, **kwargs)

def ri():
	return int(input())

def rl(f=int):
	return list(map(f, input().split()))

def rs():
	return input()

class Solution:

	def __init__(self):
		self.powers = [1]
		for i in range(1, 60):
			self.powers.append(2 ** i + self.powers[-1])

	def run(self):
		(x, y) = rl()
		if y % x != 0:
			return -1
		y //= x
		result = 0
		i = len(self.powers) - 1
		while i >= 0 and y > 0:
			while i >= 0 and self.powers[i] > y:
				i -= 1
			if i < 0:
				return -1
			result += i + 1 + 1
			y -= self.powers[i]
			i -= 1
		if y == 0:
			return result - 1
		return -1
t = int(input())
s = Solution()
for i in range(t):
	print(s.run())


import math
tc = int(input())
for _ in range(tc):
	(x, y) = list(map(int, input().split()))
	if y < x or y % x != 0:
		print(-1)
	else:
		(b, m, f) = (0, 0, 0)
		n = int(math.log2(y // x + 1))
		for i in range(n, 0, -1):
			if b + x * 2 ** i - x > y:
				continue
			b += x * 2 ** i - x
			m += i
			if b == y:
				f = 1
				break
			m += 1
		if f == 0:
			print(-1)
		else:
			print(m)


for _ in range(int(input())):
	(X, Y) = map(int, input().split())
	if Y % X > 0:
		print(-1)
	else:
		Y = Y // X
		X = 1
		T = 0
		A = []
		F = 1
		while Y > 0:
			B = bin(Y + 1)[2:]
			P = len(B) - 1
			V = 2 ** P
			Y -= V - 1
			T += P
			if P in A:
				F = 0
				break
			else:
				A.append(P)
			if Y > 0:
				T += 1
			else:
				break
		if F:
			print(T)
		else:
			print(-1)


from os import path
from io import BytesIO, IOBase
import sys
from heapq import heappush, heappop
from functools import cmp_to_key as ctk
from collections import deque, Counter, defaultdict as dd
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input().rstrip()

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

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def bo(i):
	return ord(i) - ord('0')
file = 1

def ceil(a, b):
	return (a + b - 1) // b

def solve():
	pw = [0] * 62
	pw[0] = 1
	for i in range(1, 62):
		pw[i] = 2 * pw[i - 1]
	for i in range(1, 62):
		pw[i] += pw[i - 1]
	for _ in range(ii()):
		(x, y) = mi()
		if y % x:
			print('-1')
			continue
		c = y // x
		cnt = 0
		ok = True
		x1 = set()
		while c:
			c2 = bisect_right(pw, c)
			c -= pw[c2 - 1]
			if c2 in x1:
				print('-1')
				ok = False
				break
			x1.add(c2)
			cnt += c2
			if c:
				cnt += 1
		if ok:
			print(cnt)
solve()


ref = [(1, 1)]
i = 1
while ref[i - 1][0] + (1 << i) <= 10 ** 18:
	ref.append((ref[i - 1][0] + (1 << i), i + 1))
	i += 1
for __ in range(int(input())):
	(x, y) = map(int, input().split())
	if y % x != 0:
		print(-1)
	else:
		target = y // x
		(count, ans) = (0, 0)
		for i in reversed(range(len(ref))):
			if ref[i][0] <= target:
				ans += ref[i][1]
				target -= ref[i][0]
				count += 1
		if target == 0:
			print(ans + (count - 1))
		else:
			print(-1)


a = [1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727, 268435455, 536870911, 1073741823, 2147483647, 4294967295, 8589934591, 17179869183, 34359738367, 68719476735, 137438953471, 274877906943, 549755813887, 1099511627775, 2199023255551, 4398046511103, 8796093022207, 17592186044415, 35184372088831, 70368744177663, 140737488355327, 281474976710655, 562949953421311, 1125899906842623, 2251799813685247, 4503599627370495, 9007199254740991, 18014398509481983, 36028797018963967, 72057594037927935, 144115188075855871, 288230376151711743, 576460752303423487, 1152921504606846975, 2305843009213693951, 4611686018427387903, 9223372036854775807, 18446744073709551615, 36893488147419103231, 73786976294838206463]
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	if y % x != 0:
		print(-1)
		continue
	y //= x
	j = len(a) - 1
	c = 0
	s = 0
	while j != -1:
		while j != -1 and a[j] > y:
			j -= 1
		if j == -1:
			break
		c += 1
		y -= a[j]
		s += len(bin(a[j])[2:])
		j -= 1
	if y:
		print(-1)
	else:
		print(s + c - 1)


import sys
import math

def input():
	return sys.stdin.readline().replace('\n', '').strip()
for _ in range(int(input())):
	(x, y) = list(map(int, input().split()))
	if y % x != 0:
		print(-1)
	else:
		a1 = y // x
		k = 1
		while True:
			a1 = y // x + k
			if a1 % 2 == 0:
				s1 = str(bin(a1))[2:]
				if k == s1.count('1'):
					ans = k - 1
					s1 = s1[::-1]
					for i in range(len(s1)):
						if s1[i] == '1':
							ans += i
					print(ans)
					break
				k += 2
			else:
				k += 1
			if k > math.log(a1, 2):
				print(-1)
				break


def solve(x, y, ans):
	if y % x != 0:
		ans.append('-1')
		return
	y = y // x
	min_minutes = float('inf')
	for k in range(1, 66):
		y_bin = bin(y + k)[2:]
		if y_bin.count('1') == k:
			minutes = 0
			y_bin = y_bin[::-1]
			for j in range(len(y_bin)):
				if y_bin[j] == '1':
					minutes += j
			min_minutes = min(min_minutes, minutes + k - 1)
	if min_minutes == float('inf'):
		ans.append('-1')
		return
	ans.append(str(min_minutes))

def main():
	t = int(input())
	ans = []
	for i in range(t):
		(x, y) = map(int, input().split())
		solve(x, y, ans)
	print('\n'.join(ans))
main()


for _ in range(int(input())):
	(X, Y) = map(int, input().split())
	alpha = []
	m = 1
	while m * X <= Y:
		alpha.append(m * X)
		m = 2 * m + 1
	cnt = 0
	for i in range(len(alpha) - 1, -1, -1):
		if alpha[i] <= Y:
			Y -= alpha[i]
			cnt += i + 2
	cnt -= 1
	if Y != 0:
		print(-1)
	else:
		print(cnt)


li = [2 ** i - 1 for i in range(1, 61)]

def sure(m):
	seen = []
	i = 60
	for it in li[-1::-1]:
		if it <= m:
			m -= it
			seen.append(i)
		if m == 0:
			break
		i -= 1
	if m != 0:
		return (False, [])
	return (True, seen)

def func(x, y):
	if y % x:
		return -1
	d = y // x
	(st, li) = sure(d)
	if not st:
		return -1
	ans = sum(li) + len(li) - 1
	return ans

def isSubsetSum(Set, n, sm):
	subset = [[False for i in range(sm + 1)] for i in range(n + 1)]
	for i in range(n + 1):
		subset[i][0] = True
	for i in range(1, sm + 1):
		subset[0][i] = False
	for i in range(1, n + 1):
		for j in range(1, sm + 1):
			if j < Set[i - 1]:
				subset[i][j] = subset[i - 1][j]
			if j >= Set[i - 1]:
				subset[i][j] = subset[i - 1][j] or subset[i - 1][j - Set[i - 1]]
	return subset[n][sm]
for i in range(1, 0):
	if isSubsetSum(li, len(li), i):
		print(i)
		print(func(1, i))
		input()
	elif func(1, i) == -1:
		continue
	else:
		print('BAD', i)
		input()
t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	print(func(x, y))