Read problems statements in Mandarin Chinese  and Russian. 

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 ≤ 10^{5}$
$1 ≤ i,j ≤ 10^{9}$

----- Sample Input 1 ------ 
3
1 2
2 3
4 3
----- Sample Output 1 ------ 
1
2
3
----- explanation 1 ------ 
For first query, 1 is directly connected to 2 by an edge. Hence distance 1.

Difficulty: MEDIUM
Tags: Bit manipulation

Graph algorithms

Tree algorithms

Mathematics

Data structures

Tree queries
Skill types: Bit manipulation

Data structures

Starter code:

Solutions:
z = int(input())
while z:
	cout = 0
	(x, y) = map(int, input().split())
	while x != y:
		if x > y:
			x = x // 2
			cout = cout + 1
		if x < y:
			y = y // 2
			cout = cout + 1
	print(cout)
	z -= 1


for _ in range(int(input())):
	(A, B) = map(int, input().split())
	binA = bin(A)[2:]
	binB = bin(B)[2:]
	i = 0
	k = min(len(binA), len(binB))
	while i < k and binA[i] == binB[i]:
		i += 1
	print(len(binB) + len(binA) - 2 * i)


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


def shortestlenght(n):
	c = 0
	i = 1
	while i:
		if n[-i] == n[-(i + 1)]:
			break
		else:
			c += 1
			i += 1
	return c
for _ in range(int(input())):
	(i, j) = map(int, input().split())
	pathi = []
	while i or j:
		if i >= 1:
			pathi.append(i)
			i //= 2
		if j >= 1:
			pathi.append(j)
			j //= 2
	pathi.sort()
	dis = shortestlenght(pathi)
	print(dis)


n = int(input())

def get_min_len(i, j):
	if i == j:
		return 0
	i_ancestors = {i: 0}
	j_ancestors = {j: 0}
	(count_i, count_j) = (0, 0)
	while True:
		if j != 1:
			j = j // 2
			count_j += 1
			j_ancestors[j] = count_j
		if i != 1:
			i = i // 2
			count_i += 1
			i_ancestors[i] = count_i
		if i in j_ancestors:
			return j_ancestors[i] + i_ancestors[i]
		if j in i_ancestors:
			return j_ancestors[j] + i_ancestors[j]
while n > 0:
	(i, j) = [int(x) for x in str(input()).split(' ')]
	n -= 1
	print(get_min_len(i, j))


def solve(n, m):
	cnti = 0
	cntj = 0
	while True:
		if n > m:
			while n > 1 and n > m:
				n = n >> 1
				cnti += 1
		elif m > n:
			while m > 1 and m > n:
				m = m >> 1
				cntj += 1
		else:
			return cntj + cnti
T = int(input())
for i in range(T):
	(n, m) = map(int, input().split())
	print(solve(n, m))


t = int(input(''))
for _ in range(t):
	(i, j) = map(int, input('').split())

	def counting(i, j, count):
		if i > j:
			count += 1
			return counting(i // 2, j, count)
		elif i < j:
			count += 1
			return counting(i, j // 2, count)
		elif i == j:
			return count
	print(counting(i, j, 0))


t = int(input())
while t > 0:
	(p, q) = map(int, input().split())
	c = 0
	while p != q:
		if p > q:
			p = p // 2
		else:
			q = q // 2
		c += 1
	print(c)
	t -= 1


n = int(input())
for i in range(n):
	(i, j) = list(map(int, input().split()))
	maxi = max(i, j)
	mini = min(i, j)
	count = 0
	while True:
		if maxi == mini:
			break
		else:
			maxi = maxi // 2
			count += 1
			if maxi != max(maxi, mini):
				(maxi, mini) = (mini, maxi)
	print(count)


T = int(input())
for l in range(T):
	(i, j) = map(int, input().split(' '))
	(x, y) = (bin(i)[2:], bin(j)[2:])
	s = 0
	if len(x) > len(y):
		for k in range(len(x) - len(y)):
			i = i // 2
			s += 1
	elif len(y) > len(x):
		for k in range(len(y) - len(x)):
			j = j // 2
			s += 1
	while i != j:
		i = i // 2
		j = j // 2
		s += 2
	print(s)


for _ in range(int(input())):
	(n1, n2) = map(int, input().split())
	count = 0
	while n1 != n2:
		if n1 > n2:
			n1 //= 2
		else:
			n2 //= 2
		count += 1
	print(count)


import math

def lca(i, j):
	while i != j:
		if i > j:
			i //= 2
		else:
			j //= 2
	return i

def distance(i, j):
	lca_node = lca(i, j)
	depth_i = int(math.log2(i))
	depth_j = int(math.log2(j))
	depth_lca = int(math.log2(lca_node))
	return depth_i + depth_j - 2 * depth_lca
n = int(input())
for i in range(n):
	(i, j) = map(int, input().split())
	print(distance(i, j))


n = int(input())
for i in range(n):
	nodes = [int(x) for x in input().split()]
	length = 0
	while nodes[0] != nodes[1]:
		if nodes[0] > nodes[1]:
			nodes[0] = nodes[0] // 2
		else:
			nodes[1] = nodes[1] // 2
		length += 1
	print(length)


from math import sqrt, ceil, floor, gcd, log2
import sys
from sys import stdin, stdout
from collections import Counter, defaultdict, OrderedDict, deque
from itertools import combinations, groupby
from time import time
from heapq import heappop, heappush, heapify
t = int(input())
for _ in range(t):
	(l, r) = map(int, input().split())
	cnt = 0
	while l != r:
		if l > r:
			l = l // 2
		else:
			r = r // 2
		cnt += 1
	print(cnt)


t = int(input())
for i in range(t):
	(i, j) = list(map(int, input().split()))
	count = 0
	while i != j:
		if i > j:
			i //= 2
		else:
			j //= 2
		count += 1
	print(count)


for i in range(int(input())):
	(i, j) = map(int, input().split(' '))
	edge = 0
	while i != j:
		edge += 1
		if i > j:
			i = i // 2
		else:
			j = j // 2
	print(edge)


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	a = max(a, b) + min(a, b)
	b = min(b, a - b)
	a = a - b
	sa = bin(a).replace('0b', '')
	sb = bin(b).replace('0b', '')
	lca = 0
	for i in range(len(sb)):
		if sa[i] == sb[i]:
			lca += 1
		else:
			break
	print(len(sa) + len(sb) - 2 * lca)


n = int(input())
while n != 0:
	(a, b) = map(int, input().split())
	c = 0
	while a != b:
		if a > b:
			a = int(a / 2)
		else:
			b = int(b / 2)
		c += 1
	print(c)
	n -= 1


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


def main():
	from sys import stdin, stdout
	from collections import Counter
	t = int(stdin.readline())

	def f(a, b, c=0):
		while 1:
			if a == b:
				return c
			elif a > b:
				a >>= 1
				c += 1
			else:
				b >>= 1
				c += 1
	for i in range(t):
		(a, b) = map(int, stdin.readline().split())
		stdout.write(str(f(a, b)) + '\n')
main()


for _ in range(int(input())):
	(n1, n2) = map(int, input().split())
	l1 = []
	l2 = []
	l1.append(n1)
	l2.append(n2)
	while n1 >= 1:
		n1 //= 2
		if n1 < 1:
			break
		l1.append(n1)
	while n2 >= 1:
		n2 //= 2
		if n2 < 1:
			break
		l2.append(n2)
	s1 = set(l1)
	s2 = set(l2)
	print(len(s1.union(s2) - s1.intersection(s2)))


def get_depth(node):
	depth = 0
	while node > 1:
		node = node // 2
		depth += 1
	return depth

def find_lca(i, j):
	if i == j:
		return i
	i_depth = get_depth(i)
	j_depth = get_depth(j)
	if i_depth < j_depth:
		j = j // 2 ** (j_depth - i_depth)
	elif i_depth > j_depth:
		i = i // 2 ** (i_depth - j_depth)
	while i != j:
		i = i // 2
		j = j // 2
	return i

def main():
	n = int(input().strip())
	for _ in range(n):
		(i, j) = map(int, input().strip().split())
		lca = find_lca(i, j)
		print(get_depth(i) + get_depth(j) - 2 * get_depth(lca))
main()


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


for i in range(int(input())):
	(i, j) = map(int, input().split())
	(si, sj) = (bin(i).replace('0b', ''), bin(j).replace('0b', ''))
	y = min(len(si), len(sj))
	for i in range(y):
		if si[i] != sj[i]:
			k = i
			break
	else:
		k = y
	print(len(si) + len(sj) - 2 * k)


t = int(input())
while t > 0:
	(x, y) = list(map(int, input().split(' ')))
	s1 = {x}
	s2 = {y}
	while x >= 1:
		x //= 2
		if x < 1:
			break
		s1.add(x)
	while y >= 1:
		y //= 2
		if y < 1:
			break
		s2.add(y)
	print(len(s1.union(s2) - s1.intersection(s2)))
	t -= 1


import math

def get_path(node):
	path = []
	while node > 0:
		path.append(node)
		node //= 2
	return path[::-1]

def lca(i, j):
	path_i = get_path(i)
	path_j = get_path(j)
	min_len = min(len(path_i), len(path_j))
	lca = 1
	for k in range(min_len):
		if path_i[k] == path_j[k]:
			lca = path_i[k]
		else:
			break
	return lca

def shortest_path(i, j):
	lca_node = lca(i, j)
	path_i = get_path(i)
	path_j = get_path(j)
	return len(path_i) + len(path_j) - 2 * len(get_path(lca_node))
n = int(input())
for _ in range(n):
	(i, j) = map(int, input().split())
	print(shortest_path(i, j))


def count_steps(start, end):
	binary_start = bin(start)[2:]
	binary_end = bin(end)[2:]
	steps = 0
	while binary_end.find(binary_start):
		binary_start = binary_start[:-1]
		steps += 1
	while not binary_start == binary_end:
		binary_end = binary_end[:-1]
		steps += 1
	print(steps)

def main():
	N = int(input())
	for n in range(N):
		(i, j) = map(int, input().split())
		if j > i:
			(i, j) = (j, i)
		count_steps(i, j)
main()


def get_depth(node):
	d = 0
	while node != 1:
		node //= 2
		d += 1
	return d

def spbt(i, j):
	gi = get_depth(i)
	gj = get_depth(j)
	dist = 0
	while i != j:
		if gi > gj:
			i //= 2
			gi -= 1
		else:
			j //= 2
			gj -= 1
		dist += 1
	return dist
t = int(input())
for _ in range(t):
	(i, j) = map(int, input().split())
	print(spbt(i, j))


x = int(input())
t = []
for nnb in range(0, x):
	lp = str(input())
	yyr = []
	lp = lp.split(' ')
	for vvc in lp:
		yyr.append(int(vvc))
	t.append(yyr)
for r in t:
	a = r[0]
	b = r[1]
	pat = 0
	k = 0
	while 2 ** k <= a:
		k += 1
	k -= 1
	bl = 0
	while 2 ** bl <= b:
		bl += 1
	bl -= 1
	lprt = a
	temp = b
	if k != bl:
		lprt = None
		if a > b:
			lprt = a
			temp = b
		elif b > a:
			lprt = b
			temp = a
		df = None
		ck = None
		if k > bl:
			df = k
			ck = bl
		elif bl > k:
			df = bl
			ck = k
		while df != ck:
			if lprt % 2 == 0:
				lprt = lprt // 2
			else:
				lprt = (lprt - 1) // 2
			df -= 1
			pat += 1
	indi = 0
	if temp == lprt:
		indi = 1
	while indi == 0:
		if temp % 2 == 0 and temp != 1:
			temp = temp // 2
			pat += 1
		elif temp % 2 != 0 and temp != 1:
			temp = (temp - 1) // 2
			pat += 1
		if lprt % 2 == 0 and lprt != 1:
			lprt = lprt // 2
			pat += 1
		elif lprt % 2 != 0 and lprt != 1:
			lprt = (lprt - 1) // 2
			pat += 1
		if lprt == temp:
			break
	print(pat)


import math
t = int(input())
for i in range(t):
	(i, j) = map(int, input().split())
	ct = 0
	while i != j:
		if i > j:
			i = i // 2
		else:
			j = j // 2
		ct += 1
	print(ct)


t = int(input())
while t:
	(n, m) = map(int, input().split())
	count = 0
	while n != m:
		if n > m:
			n = int(n / 2)
		else:
			m = int(m / 2)
		count += 1
	print(count)
	t -= 1


import datetime as dt
n = int(input())
for i in range(n):
	pos = [int(j) for j in input().split(' ')]
	step = 0
	while True:
		if pos[0] == pos[1]:
			print(step)
			break
		elif pos[0] > pos[1]:
			pos[0] = pos[0] // 2
		else:
			pos[1] = pos[1] // 2
		step += 1


x = int(input())
for _ in range(x):
	count = 0
	(x, y) = map(int, input().split())
	while x != y:
		if x > y:
			x = x // 2
			count = count + 1
		if x < y:
			y = y // 2
			count = count + 1
	print(count)


for _ in range(int(input())):
	(i, j) = map(int, input().split(' '))
	edge = 0
	while i != j:
		edge += 1
		if i > j and i > 1:
			i = i // 2
		elif i < j and j > 1:
			j = j // 2
	print(edge)


def solve(a, b):
	(l, m) = [[], []]
	while a * b > 1:
		if a > 1:
			l.append(a)
			a //= 2
		if b > 1:
			m.append(b)
			b //= 2
	l = set(l)
	m = set(m)
	n = len(l.union(m))
	n2 = len(l.intersection(m))
	print(n - n2)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	solve(a, b)


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


t = int(input())
while t:
	c = 0
	(i, j) = map(int, input().split())
	while True:
		if i > j:
			i >>= 1
			c += 1
		elif i < j:
			j >>= 1
			c += 1
		else:
			break
	print(c)
	t -= 1


t = int(input())

def parent(k):
	if k == 1:
		return 1
	else:
		return k // 2
while t:
	(i, j) = map(int, input().split())
	c = 0
	while i != j:
		if i > j:
			i = parent(i)
		else:
			j = parent(j)
		c = c + 1
	print(c)
	t = t - 1


from math import log2

def solve(a, b, la, lb):
	if a == b:
		return 0
	if la > lb:
		a //= 2
		la -= 1
		return solve(a, b, la, lb) + 1
	if la < lb:
		b //= 2
		lb -= 1
		return solve(a, b, la, lb) + 1
	a //= 2
	b //= 2
	la -= 1
	lb -= 1
	return solve(a, b, la, lb) + 2
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	(la, lb) = (int(log2(a)), int(log2(b)))
	print(solve(a, b, la, lb))


def solve():
	(a, b) = [int(x) for x in input().split()]
	d = 0
	while a != b:
		if a > b:
			a //= 2
		else:
			b //= 2
		d += 1
	print(d)
T = int(input())
while T:
	solve()
	T -= 1


n = int(input())
for x in range(n):
	(i, j) = map(int, input().split())
	list1 = []
	while i != 1:
		list1.insert(0, i)
		i = i // 2 if i % 2 == 0 else (i - 1) // 2
	list1.insert(0, 1)
	list2 = []
	while j != 1:
		list2.insert(0, j)
		j = j // 2 if j % 2 == 0 else (j - 1) // 2
	list2.insert(0, 1)
	for i in range(min(len(list1), len(list2))):
		if list1[i] != list2[i]:
			i -= 1
			break
	dist = len(list1) - 1 - i + len(list2) - 1 - i
	print(dist)


for tc in range(int(input())):
	(a, b) = map(int, input().split())
	(s1, s2) = ([], [])
	while a:
		s1.append(a)
		a = a // 2
	while b:
		s2.append(b)
		b = b // 2
	s1 = set(s1)
	s2 = set(s2)
	ans = len(s1.union(s2)) - len(s1.intersection(s2))
	print(ans)


def fun(i, j, count):
	if i > j:
		return fun(i // 2, j, count + 1)
	elif i < j:
		return fun(i, j // 2, count + 1)
	else:
		return count
t = int(input())
for _ in range(t):
	(i, j) = map(int, input().split())
	d = fun(i, j, 0)
	print(d)


n = int(input())
for i in range(n):
	(x, y) = map(int, input().split())
	count = 0
	while x != y:
		if x > y:
			x = x // 2
			count += 1
		else:
			y = y // 2
			count += 1
	print(count)