Read problems statements in Mandarin Chinese  and Russian. 

Chef is on a vacation these days, so his friend Chefza is trying to solve Chef's everyday tasks.
Today's task is to make a sweet roll. Rolls are made by a newly invented cooking machine. The machine is pretty universal - it can make lots of dishes and Chefza is thrilled about this.
To make a roll, Chefza has to set all the settings to specified integer values. There are lots of settings, each of them set to some initial value. The machine is pretty complex and there is a lot of cooking to be done today, so Chefza has decided to use only two quick ways to change the settings. In a unit of time, he can pick one setting (let's say its current value is v) and change it in one of the following ways.

If v is even, change this setting to v/2. If v is odd, change it to (v − 1)/2.
Change setting to 2 × v

The receipt is given as a list of integer values the settings should be set to. It is guaranteed that each destination setting can be represented as an integer power of 2.
Since Chefza has just changed his profession, he has a lot of other things to do. Please help him find the minimum number of operations needed to set up a particular setting of the machine. You can prove that it can be done in finite time.

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

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The only line of each test case contains two integers A and B denoting the initial and desired values of the setting, respectively.

------ Output ------ 

For each test case, output a single line containing minimum number of operations Chefza has to perform in order to set up the machine.

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

$1 ≤ T ≤ 200$
$1 ≤ A ≤ 10^{7}$
$1 ≤ B ≤ 10^{7}, and B is an integer power of 2$

------ Subtasks ------ 

$Subtask #1 [40 points]: A ≤ 100 and B ≤ 100$
$Subtask #2 [60 points]: No additional constraints$

----- Sample Input 1 ------ 
6
1 1
2 4
3 8
4 16
4 1
1 4
----- Sample Output 1 ------ 
0
1
4
2
2
2
----- explanation 1 ------ 

In the first test case, you don't need to do anything.
In the second test case, you need to multiply 2 by 2 and get 4. This is done in 1 operation.
In the third test case, you need to obtain 1 from 3 and then multiply it by 2 three times to obtain 8. A total of 4 operations.
In the fourth test case, multiply 4 by 2 twice.
In the fifth test case, divide 4 by 2 twice.
In the sixth test case, multiply 1 by 2 twice.

Source: codechef | Difficulty: EASY
Tags: Bit manipulation

Ad-hoc


Solutions:
for i in range(int(input())):
	(a, b) = map(int, input().split())
	count = 0
	while b % a != 0:
		a = a // 2
		count = count + 1
	while a != b:
		a = a * 2
		count = count + 1
	print(count)


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


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	step = 0
	while b % a != 0:
		a = a // 2
		step += 1
	while a != b:
		a = a * 2
		step += 1
	print(step)


n = input()
n = int(n)
for i in range(0, n):
	(a, b) = input().split()
	a = int(a)
	b = int(b)
	c = 0
	while b % a != 0:
		if a % 2 == 0:
			a = a // 2
		else:
			a = (a - 1) // 2
		c += 1
	while a != b:
		a = a * 2
		c += 1
	print(c)


for _ in range(int(input())):
	(a, b) = [int(x) for x in input().split()]
	cnt = 0
	while a != b:
		if a > b:
			if a % 2 == 0:
				a //= 2
			else:
				a = (a - 1) // 2
			cnt += 1
		else:
			if b % 2 == 0:
				b //= 2
			else:
				b = (b - 1) // 2
			cnt += 1
	print(cnt)


t = int(input())
while t:
	(a, b) = [int(i) for i in input().split()]
	ca = 0
	cb = 0
	cnt = 0
	while a & a - 1 != 0 or a > b:
		if a % 2 == 0:
			a //= 2
			cnt += 1
		else:
			a = (a - 1) // 2
			cnt += 1
	if a != 1:
		while a > 1:
			a //= 2
			ca += 1
	if b != 1:
		while b > 1:
			b //= 2
			cb += 1
	print(cnt + cb - ca)
	t -= 1


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	c = 0
	while a != b:
		k = list(bin(a))
		if k.count('1') == 1:
			if a < b:
				a *= 2
			else:
				a //= 2
		elif a % 2 == 1:
			a = (a - 1) // 2
		else:
			a //= 2
		c += 1
	print(c)


def cook(a, b):
	c = 0
	if a < b:
		while a != b:
			if b % a == 0:
				a = a * 2
				c = c + 1
			elif a % 2 == 0:
				a = a / 2
				c = c + 1
			else:
				a = (a - 1) / 2
				c = c + 1
		print(c)
	elif a > b:
		while a != b:
			if b % a == 0:
				a = a * 2
				c = c + 1
			elif a % 2 == 0:
				a = a / 2
				c = c + 1
			else:
				a = (a - 1) / 2
				c = c + 1
		print(c)
	else:
		print(0)
t = int(input())
for i in range(t):
	(a, b) = map(int, input().strip().split())
	cook(a, b)


n = int(input())
import math
for i in range(n):
	(A, B) = map(int, input().split())
	ctr = 0
	while B % A != 0:
		A = A // 2
		ctr += 1
	while A != B:
		A = A * 2
		ctr += 1
	print(ctr)


from math import log2
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	c = int(log2(b))
	d = 0
	e = 0
	t = a
	while int(log2(t)) != log2(t):
		t = t // 2
		d += 1
	d += abs(int(log2(t)) - c)
	print(d)


t = input()
for c in range(0, int(t)):
	(a, b) = map(int, input().split())
	steps = 0
	while b % a != 0:
		if a % 2 == 0:
			a = a // 2
		else:
			a = (a - 1) // 2
		steps += 1
	while a != b:
		a = a * 2
		steps += 1
	print(steps)


cases = int(input())
for case in range(cases):
	(a, b) = map(int, input().split())
	steps = 0
	while b % a != 0:
		if a % 2 == 0:
			a = a // 2
		else:
			a = (a - 1) // 2
		steps += 1
	while a != b:
		a = a * 2
		steps += 1
	print(steps)


T = int(input())
for i in range(T):
	l1 = [int(x) for x in input().split()]
	A = l1[0]
	B = l1[1]
	r = 0
	while A != B:
		if A > B:
			A = A // 2
		else:
			B = B // 2
		r = r + 1
	print(r)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	c = 0
	while True:
		if a == b:
			break
		if a > b:
			a = a // 2
			c += 1
		if b > a:
			b = b // 2
			c += 1
	print(c)


import math
for _ in range(int(input())):
	(a, b) = list(map(int, input().split()))
	if a == b:
		print(0)
	else:
		c = 0
		while a != b:
			if a and (not a & a - 1) and (b > a):
				c += int(math.log2(b) - math.log2(a))
				break
			if a & 1:
				a = (a - 1) // 2
				c += 1
			else:
				a = a // 2
				c += 1
		print(c)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	q = [[a, 0]]
	vis = set()
	while q:
		t = q.pop(0)
		if t[0] == b:
			print(t[1])
			break
		if t[0] * 2 == b or t[0] // 2 == b:
			print(t[1] + 1)
			break
		if t[0] * 2 not in vis and t[0] * 2 <= 3 * 10 ** 7:
			q.append([t[0] * 2, t[1] + 1])
			vis.add(t[0] * 2)
		if t[0] // 2 not in vis and t[0] // 2 > 0:
			q.append([t[0] // 2, t[1] + 1])
			vis.add(t[0] // 2)


try:
	from math import log
	for _ in range(int(input())):
		(a, b) = map(int, input().split())
		cnt = 0
		while a != b:
			if b % a == 0:
				a = a * 2
			else:
				a = a // 2
			cnt += 1
		print(cnt)
except EOFError:
	pass


def count_set_bits(n):
	count = 0
	while n:
		n &= n - 1
		count += 1
	return count
t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	res = 0
	while count_set_bits(a) > 1:
		a = a // 2
		res = res + 1
	while a < b:
		a = a * 2
		res = res + 1
	while a > b:
		a = a // 2
		res = res + 1
	print(res)


for _ in range(int(input())):
	(given, target) = map(int, input().split())
	if given == target:
		print(0)
		continue
	elif given > target:
		c = 0
		while given > target:
			given = given // 2
			c += 1
		while given & given - 1 != 0:
			given = given // 2
			c += 1
		while given != target:
			given = given << 1
			c += 1
		print(c)
		continue
	else:
		c = 0
		while given & given - 1 != 0:
			given = given // 2
			c += 1
		while given != target:
			given = given << 1
			c += 1
		print(c)
		continue


import math

def check(a, x):
	d = math.log2(a)
	if d.is_integer():
		return (a, x)
	else:
		x += 1
		return check(a // 2, x)
t = int(input(''))
if 1 <= t <= 200:
	for _ in range(t):
		(a, b) = map(int, input().split())
		c = math.log2(b)
		if 1 <= a <= 10 ** 7 and 1 <= b <= 10 ** 7 and c.is_integer():
			(a, x) = check(a, 0)
			if a > b:
				x += int(math.log2(a // b))
			else:
				x += int(math.log2(b // a))
			print(x)


import math
T = int(input())
for t in range(T):
	(a, b) = map(int, input().split())
	if a == b:
		print(0)
	else:
		count = 0
		while a != b:
			if a < b:
				b //= 2
			elif a > b:
				a //= 2
			count += 1
		print(count)


def main(a, b):
	count = 0
	while not b % a == 0:
		a >>= 1
		count += 1
	while not b == a:
		a <<= 1
		count += 1
	return count
t = int(input())
for _ in range(t):
	(i, f) = list(map(int, input().split()))
	print(main(i, f))


import math
testcase = int(input())
for i in range(testcase):
	(x, y) = map(int, input().split())
	op = 0
	while math.floor(math.log2(x)) != math.log2(x):
		x //= 2
		op += 1
	op = op + abs(math.log2(y) - math.log2(x))
	print(int(op))


def solve(a, b):
	if b % a == 0:
		d = b // a
		if d % 2 == 0 or d == 1:
			i = 0
			while d != 1:
				d //= 2
				i += 1
			return i
	else:
		return solve(a // 2, b) + 1
T = int(input())
for _ in range(T):
	(a, b) = map(int, input().split())
	print(solve(a, b))


for i in range(0, int(input())):
	a = list(map(int, input().split()))
	r = 0
	while a[1] % a[0] != 0:
		a[0] = a[0] // 2
		r += 1
	while a[1] != a[0]:
		a[0] = a[0] * 2
		r += 1
	print(r)


t = int(input())
while t > 0:
	(a, b) = map(int, input().split(' '))
	count = 0
	while b % a != 0:
		a = a // 2
		count += 1
	while a != b:
		a *= 2
		count += 1
	print(count)
	t -= 1


from math import log2
for _ in range(int(input())):
	(A, B) = map(int, input().split())
	ans = 0
	while B % A != 0:
		A //= 2
		ans += 1
	print(int(log2(B // A)) + ans)


import math
t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	sol = 0
	while b % a != 0:
		a //= 2
		sol += 1
	while a != b:
		a *= 2
		sol += 1
	print(sol)


def check(a, b):
	counter = 0
	while a != b:
		if b % a == 0:
			a *= 2
		elif a & 1 == 1 and a != 1:
			a -= 1
			a >>= 1
		else:
			a >>= 1
		counter += 1
	print(counter)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	check(a, b)


from math import log
for __ in range(int(input())):
	(a, b) = map(int, input().split())
	answer = 0
	while b % a != 0:
		a //= 2
		answer += 1
	answer += int(log(b // a, 2))
	print(answer)


from math import log2
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	ans = 0
	while a != b:
		if a > b:
			a //= 2
			ans += 1
		else:
			c = log2(a)
			if c == int(c):
				a *= 2
			else:
				a //= 2
			ans += 1
	print(ans)


t = int(input())
for t in range(0, t):
	q = list(map(int, input().rstrip().split()))
	a = q[0]
	b = q[1]
	n = a
	m = b
	o = 0
	while a != b:
		if a < b and b % 2 == 0:
			b = b // 2
			o += 1
		elif b < a and a % 2 == 0:
			a = a // 2
			o += 1
		elif a < b and a % 2 != 0:
			b = (b - 1) // 2
			o += 1
		elif b < a and a % 2 != 0:
			a = (a - 1) // 2
			o += 1
	if n == m:
		print(0)
	else:
		print(o)


from math import log
t = int(input())
for ni in range(t):
	(a, b) = map(int, input().split())
	count = 0
	while b % a != 0:
		a = a // 2
		count = count + 1
	print(count + int(log(b // a, 2)))


two_powers = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912]
for i in range(int(input())):
	(bharat, jaapan) = map(int, input().split(' '))
	if bharat == jaapan:
		print('0')
		continue
	if bharat in two_powers and jaapan in two_powers:
		south_asia = two_powers.index(bharat)
		east_asia = two_powers.index(jaapan)
		print(abs(south_asia - east_asia))
		continue
	else:
		counter = 0
		if bharat not in two_powers:
			condition = True
			while condition == True:
				if bharat in two_powers and jaapan in two_powers:
					south_asia = two_powers.index(bharat)
					east_asia = two_powers.index(jaapan)
					print(abs(south_asia - east_asia) + counter)
					condition = False
					continue
				elif bharat % 2 == 0:
					counter = counter + 1
					bharat = bharat / 2
					continue
				elif bharat % 2 == 1:
					counter = counter + 1
					bharat = bharat - 1
					bharat = bharat / 2
					if bharat in two_powers and jaapan in two_powers:
						south_asia = two_powers.index(bharat)
						east_asia = two_powers.index(jaapan)
						print(abs(south_asia - east_asia) + counter)
						condition = False
						continue


t = int(input())
for t in range(t):
	(a, b) = [int(i) for i in input().split()]
	count = 0
	if a == b:
		count = 0
	else:
		while b % a != 0:
			a = a // 2
			count += 1
		while a != b:
			a = a * 2
			count += 1
	print(count)


import math
for i in range(int(input())):
	(a, b) = map(int, input().split())
	c = 0
	while a != b:
		if b % a == 0:
			c += int(math.log2(b // a))
			break
		elif a % 2 == 0:
			a = a // 2
		elif a % 2 != 0:
			a = (a - 1) // 2
		c += 1
	print(c)


import math
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	count = 0
	while float(math.log(a, 2)) != math.floor(math.log(a, 2)):
		if a % 2 == 0:
			a = a // 2
		else:
			a = (a - 1) // 2
		count += 1
	count += abs(math.log(b, 2) - math.log(a, 2))
	print(int(count))


for _ in range(int(input())):
	(s, d) = map(int, input().split())
	res = 0
	while True:
		if s == d:
			break
		elif s > d:
			s //= 2
			res += 1
		elif s < d:
			d //= 2
			res += 1
		else:
			pass
	print(res)


import math
tests = int(input())
for i in range(tests):
	(initial, final) = map(int, input().split())
	ans = 0
	while int(math.log(initial, 2)) != math.log(initial, 2):
		if initial & 1:
			initial = (initial - 1) // 2
		else:
			initial //= 2
		ans += 1
	initial_pow = int(math.log(initial, 2))
	final_pow = int(math.log(final, 2))
	print(ans + abs(initial_pow - final_pow))


import math
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	c = 0
	while a != b:
		if a > b:
			a //= 2
			c += 1
		elif a < b:
			x = int(math.log(a, 2))
			if 2 ** x == a:
				a *= 2
			else:
				a //= 2
			c += 1
	print(c)


def binrep(x):
	count = 0
	while x > 0:
		if x & 1 == 1:
			count += 1
		x >>= 1
	return count
t = int(input())
while t > 0:
	(a, b) = map(int, input().split())
	c = 0
	while binrep(a) != 1:
		if a % 2 == 0:
			a = a // 2
		else:
			a = (a - 1) // 2
		c += 1
	if a > b:
		while a != b:
			a = a // 2
			c += 1
	elif a < b:
		while a != b:
			a = a * 2
			c += 1
	print(c)
	t -= 1


l = []
for k in range(33):
	if pow(2, k) < 10000000:
		l.append(pow(2, k))
	else:
		break
for j in range(int(input())):
	c = 0
	(a, b) = map(int, input().split())
	if a == b:
		print(0)
	elif a == 1:
		print(l.index(b))
	elif a in l:
		m = l.index(a)
		n = l.index(b)
		print(abs(m - n))
	else:
		while a not in l and a != 1:
			c = c + 1
			if a % 2 == 0:
				a = int(a / 2)
			else:
				a = int((a - 1) / 2)
		if a == 1:
			print(l.index(b) + c)
		else:
			m = l.index(a)
			n = l.index(b)
			print(abs(m - n) + c)


for _ in range(int(input())):
	(i, f) = map(int, input().split())
	c = 0
	if i == f:
		print(0)
	else:
		while i != f:
			if i > f:
				i = i // 2
				c += 1
			elif f > i:
				f = f // 2
				c += 1
		print(c)


def cnt(a, b):
	count = 0
	if a > b:
		while a != b:
			count += 1
			a = a >> 1
	elif a < b:
		while a != b:
			count += 1
			a = a << 1
	return count
t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	count = 0
	while a & a - 1 != 0:
		if a & 1 == 0:
			a = a >> 1
			count += 1
		else:
			a -= 1
			a = a >> 1
			count += 1
	ans = count + cnt(a, b)
	print(ans)


import math
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	a1 = a
	b1 = b
	c = 0
	while a != b:
		if a < b and b % 2 == 0:
			b = b // 2
			c += 1
		elif b < a and a % 2 == 0:
			a = a // 2
			c += 1
		elif a < b and b % 2 != 0:
			b = (b - 1) // 2
			c += 1
		elif a > b and a % 2 != 0:
			a = (a - 1) // 2
			c += 1
	if a1 == b1:
		print(0)
	else:
		print(c)


from math import log2
for tc in range(int(input())):
	(a, b) = map(int, input().split())
	ans = 0
	if a == b:
		ans = 0
	else:
		while b % a != 0:
			a = a // 2
			ans += 1
		alog = log2(a)
		blog = log2(b)
		ans += abs(alog - blog)
	print(int(ans))


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	operation = 0
	if a == b:
		pass
	else:
		while a != b:
			if b % a == 0 and b > a:
				operation += 1
				a = a * 2
			elif b > a and b % a != 0:
				if a % 2 == 0:
					a = a // 2
					operation += 1
				else:
					a = (a - 1) // 2
					operation += 1
			elif a % 2 == 0:
				a = a // 2
				operation += 1
			else:
				a = (a - 1) // 2
				operation += 1
	print(operation)


t = int(input(''))
for i in range(t):
	l = input('').split()
	count = 0
	v = int(l[0])
	nv = int(l[1])
	while v != nv:
		if nv % v == 0:
			v = 2 * v
			count += 1
		elif v % 2 == 0:
			v = v / 2
			count += 1
		else:
			v = (v - 1) / 2
			count += 1
	print(count)


import math
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	if a == b:
		print(0)
	else:
		cnt = 0
		while a != b:
			if a and (not a & a - 1) and (b > a):
				cnt += int(math.log(b, 2) - math.log(a, 2))
				break
			if a & 1 != 1:
				a //= 2
				cnt += 1
			else:
				a = (a - 1) // 2
				cnt += 1
		print(cnt)


import math

def is_pow_two(n):
	x = n
	while x % 2 == 0:
		x = x // 2
	if x == 1:
		return True
	else:
		return False
tc = int(input())
for _ in range(tc):
	(initial, final) = [int(x) for x in input().split()]
	operations = 0
	while not is_pow_two(initial):
		if initial % 2 == 0:
			initial = initial // 2
		else:
			initial = (initial - 1) // 2
		operations += 1
	if initial >= final:
		operations += math.log(initial // final, 2)
	else:
		operations += math.log(final // initial, 2)
	print(int(operations))


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	s = 0
	while 1:
		if a == b:
			print(s)
			break
		elif b % a == 0:
			a = a * 2
		elif a % 2 == 0:
			a = a // 2
		else:
			a = (a - 1) // 2
		s += 1


import math
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	if a == b:
		print(0)
	else:
		extra = 0
		while int(math.log(a, 2)) != math.log(a, 2):
			a = a // 2
			extra = extra + 1
		ans1 = math.log(a, 2)
		ans2 = math.log(b, 2)
		print(int(abs(ans2 - ans1) + extra))


from math import log
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	if a == b:
		print(0)
	else:
		c = 0
		while a & -a != a:
			a >>= 1
			c += 1
		while a < b:
			a <<= 1
			c += 1
		while a > b:
			a >>= 1
			c += 1
		print(c)


class Chef:

	def cook(self, a, b):
		step = 0
		while b % a != 0:
			a = a // 2
			step += 1
		while a != b:
			a = a * 2
			step += 1
		return step
c = Chef()
t = int(input())
while t:
	i = list(map(int, input().strip().split()))[:2]
	a = i[0]
	b = i[1]
	print(c.cook(a, b))
	t -= 1


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	c = 0
	while a != b:
		if a > b:
			a >>= 1
		else:
			b >>= 1
		c += 1
	print(c)


t = int(input())
for i in range(t):
	A = input()
	a = int(A.split()[0])
	b = int(A.split()[1])
	count = 0
	while b % a != 0:
		a = int(a / 2)
		count = count + 1
	while a != b:
		a = a * 2
		count = count + 1
	print(count)


def check(a, b):
	count = 0
	if a < b:
		while a != b:
			if b % a == 0:
				a = a * 2
				count = count + 1
			elif a % 2 == 0:
				a = a / 2
				count = count + 1
			else:
				a = (a - 1) / 2
				count = count + 1
		print(count)
	elif a > b:
		while a != b:
			if b % a == 0:
				a = a * 2
				count = count + 1
			elif a % 2 == 0:
				a = a / 2
				count = count + 1
			else:
				a = (a - 1) / 2
				count = count + 1
		print(count)
	else:
		print(0)
t = int(input())
for i in range(t):
	(a, b) = map(int, input().strip().split())
	check(a, b)


for case in range(int(input())):
	(a, b) = map(int, input().split())
	steps = 0
	while b % a != 0:
		a = a // 2
		steps += 1
	while a != b:
		a = a * 2
		steps += 1
	print(steps)