Consider an infinite full binary tree (each node has two children except the leaf nodes) defined as follows. For a node labelled v its left child will be labelled 2*v and its right child will be labelled 2*v+1. The root is labelled as 1.
You are given N queries of the form i j. For each query, you have to print the length of the shortest path between node labelled i and  node labelled j.

-----Input-----
First line contains N, the number of queries. Each query consists of two space separated integers i and j in one line.

-----Output-----
For each query, print the required answer in one line.

-----Constraints-----
- 1 ≤ N ≤ 105
- 1 ≤ i,j ≤ 109

-----Example-----
Input:
3
1 2
2 3
4 3

Output:
1
2
3

-----Explanation-----
For first query, 1 is directly connected to 2 by an edge. Hence distance 1.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
t = eval(input())
for _ in range(t):
	(i, j) = list(map(int, input().split()))
	bi = bin(i)[2:]
	bj = bin(j)[2:]
	k = 0
	while k < min(len(bi), len(bj)):
		if bi[k] != bj[k]:
			break
		else:
			k += 1
	print(len(bi) - k + len(bj) - k)


n = int(input())
for _ in range(n):
	(x, y) = list(map(int, input().split()))
	bx = bin(x)[2:]
	by = bin(y)[2:]
	i = 0
	while i < min(len(bx), len(by)) and bx[i] == by[i]:
		i += 1
	print(len(bx) + len(by) - 2 * i)


n = int(input())
for t in range(n):
	(a, b) = [int(x) for x in input().split()]
	count = 0
	while not a == b:
		if a > b:
			a = a / 2
		else:
			b = b / 2
		count += 1
	print(count)


n = eval(input())
n = int(n)
i = 0
while i < n:
	i += 1

	def path(fr, to):
		if fr < to:
			(fr, to) = (to, fr)
		if fr == to:
			return 0
		elif fr == 1:
			return path(to, 1)
		elif fr % 2:
			up = int((fr - 1) / 2)
			return 1 + path(up, to)
		elif not fr % 2:
			up = int(fr / 2)
			return 1 + path(up, to)
	cor = input().split()
	f = int(cor[0])
	t = int(cor[1])
	print(path(f, t))


N = int(input())
for _ in range(N):
	(a, b) = list(map(int, input().split(' ')))
	distance = 0
	while a != b:
		distance += 1
		(a, b) = (a, b / 2) if a < b else (a / 2, b)
	print(distance)


import sys
import math
cache_parent = {}

def find_chain_1(num1, parent_c1):
	while True:
		if num1 in cache_parent:
			parent_c1.extend(cache_parent[num1])
			return parent_c1
		parent_c1.append(num1)
		if num1 == 1:
			return
		num1 = int(num1 / 2)

def find_chain_2(num2, parent_c2):
	while True:
		if num2 in cache_parent:
			parent_c2.extend(cache_parent[num2])
			return parent_c2
		parent_c2.append(num2)
		if num2 == 1:
			return
		num2 = int(num2 / 2)

def getlen(chain_1, chain_2, num1, num2):
	root = list(set(chain_1) & set(chain_2))
	root.sort()
	root = root[-1]
	distance = chain_1.index(root) + chain_2.index(root)
	return distance
lines = sys.stdin.readlines()
for num in lines[1:]:
	(num1, num2) = num.strip().split(' ')
	num1 = int(num1)
	num2 = int(num2)
	parent_c1 = []
	parent_c2 = []
	find_chain_1(num1, parent_c1)
	cache_parent[num1] = parent_c1
	find_chain_2(num2, parent_c2)
	cache_parent[num2] = parent_c2
	print(getlen(parent_c1, parent_c2, num1, num2))


t = int(input())
for i in range(t):
	(i, j) = list(map(int, input().split()))
	base1 = i
	base2 = j
	arr1 = []
	arr2 = []
	while base1 > 0:
		arr1.append(base1)
		base1 = base1 / 2
	while base2 > 0:
		arr2.append(base2)
		base2 = base2 / 2
	n1 = len(arr1)
	n2 = len(arr2)
	n = min(n1, n2)
	dist = -1
	for i in range(n):
		if arr1[n1 - 1 - i] != arr2[n2 - 1 - i]:
			dist = n1 + n2 - 2 * i
			break
	if dist == -1:
		dist = max(n1, n2) - n
	print(dist)


import math
n = int(input())
for i in range(0, n):
	line = input().split()
	a = int(line[0])
	b = int(line[1])
	loga = int(math.log(a, 2))
	logb = int(math.log(b, 2))
	dist = 0
	if loga > logb:
		dist += loga - logb
		a = a >> loga - logb
	else:
		b = b >> logb - loga
		dist += logb - loga
	x = a ^ b
	if x:
		dist += (int(math.log(x, 2)) + 1) * 2
	print(dist)


N = eval(input())
while N:
	N -= 1
	(a, b) = [int(x) for x in input().split()]
	count = 0
	a = bin(a)[2:]
	b = bin(b)[2:]
	j = 0
	for i in range(0, min(len(a), len(b))):
		if a[i] == b[i]:
			j = i
			continue
		else:
			count += len(a) - i
			count += len(b) - i
			break
	if j == min(len(a), len(b)) - 1:
		count += len(a) + len(b) - 2 * j - 2
	print(count)


import math
n = int(input())
for i in range(0, n):
	line = input().split()
	a = int(line[0])
	b = int(line[1])
	loga = int(math.log(a, 2))
	logb = int(math.log(b, 2))
	dist = 0
	while loga > logb:
		a = a / 2
		dist += 1
		loga -= 1
	while loga < logb:
		b = b / 2
		dist += 1
		logb -= 1
	while a != b:
		a = a / 2
		b = b / 2
		dist += 2
	print(dist)


N = eval(input())
while N:
	N -= 1
	(a, b) = [int(x) for x in input().split()]
	count = 0
	while a != b:
		if b < a:
			a = a / 2
			count += 1
		elif a < b:
			b = b / 2
			count += 1
	print(count)


n = int(input())
for j in range(n):
	(a, b) = list(map(int, input().split()))
	d = 0
	while a != b:
		if a > b:
			a /= 2
			d += 1
		else:
			b /= 2
			d += 1
	print(d)


def read_mapped(func=lambda x: x):
	return list(map(func, input().split(' ')))

def read_array(N, func):
	l = []
	for i in range(N):
		l.append(func(input()))
	return l

def read_int():
	return int(input())

def read_str():
	return input()

def read_float():
	return float(input())
T = read_int()

def solve(m, n, s):
	if m == n:
		return s
	if m < n:
		(m, n) = (n, m)
	if m % 2 == 0:
		return solve(m / 2, n, s + 1)
	else:
		return solve((m - 1) / 2, n, s + 1)
for case in range(T):
	(i, j) = read_mapped(int)
	si = min(i, j)
	sj = max(i, j)
	print(solve(sj, si, 0))


import sys
for q in range(int(sys.stdin.readline())):
	(n1, n2) = list(map(int, sys.stdin.readline().split()))
	count = 0
	while n1 != n2:
		while n1 > n2:
			n1 /= 2
			count += 1
		while n2 > n1:
			n2 /= 2
			count += 1
	print(count)


import math
import sys
import time

def getLevel(number):
	_level = math.floor(math.log(number, 2))
	return int(_level)

def isPair(number):
	return number % 2 == 0

def getInterval(a, b, max):
	_max = max
	_loop = -1
	_apart = 0
	while _apart == 0 and _max != 1:
		_loop += 1
		_max = _max >> 1
		if a < _max and b >= _max:
			_apart = 1
		elif a >= _max:
			a = a - _max
			b = b - _max
	return _loop

def resolve2(nodes):
	if nodes[0] == nodes[1]:
		return 0
	l = 0
	k = 0
	while nodes[0] != nodes[1]:
		if nodes[1] < nodes[0]:
			if nodes[0] > 1:
				nodes[0] = nodes[0] / 2 if isPair(nodes[0]) else (nodes[0] - 1) / 2
				l += 1
		elif nodes[1] > 1:
			nodes[1] = nodes[1] / 2 if isPair(nodes[1]) else (nodes[1] - 1) / 2
			k += 1
	return l + k

def __starting_point():
	step = 0
	for line in sys.stdin:
		if step == 0:
			step = 1
			continue
		nodes = [int(nums) for nums in line.strip().split()]
		if nodes[0] == nodes[1]:
			print(0)
			continue
		_temp = nodes[0]
		if nodes[0] < nodes[1]:
			nodes[0] = nodes[1]
			nodes[1] = _temp
		_max_level = getLevel(nodes[0])
		if nodes[1] == 1:
			print(_max_level)
			continue
		_min_level = getLevel(nodes[1])
		substract = _max_level - _min_level
		if substract != 0:
			nodes[0] = nodes[0] >> substract
		_temp = nodes[0]
		if nodes[0] < nodes[1]:
			nodes[0] = nodes[1]
			nodes[1] = _temp
		if nodes[1] == nodes[0]:
			print(substract)
			continue
		_max = 2 ** _min_level
		apart = getInterval(nodes[1] - _max, nodes[0] - _max, _max)
		print(2 * (_min_level - apart) + substract)
__starting_point()