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: interview

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)


#!/usr/bin/python

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):
 """if len(chain_1) > len(chain_2):
     shorter = chain_2
     larger = chain_1
    else:
     shorter = chain_1
     larger = chain_2
    for i in shorter:
     if i in larger:
      root = i
      break"""
 root = list(set(chain_1) & set(chain_2))
 root.sort()
 root = root[-1]
 #distance = int(math.log(num1, 2) + 1) + int(math.log(num2, 2) + 1)   - 2        *int(math.log(root, 2)+1)
 #print root
 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
 #print parent_c1 
 find_chain_2(num2, parent_c2)
 cache_parent[num2] = parent_c2
 #print 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
 #print a, b
 if loga > logb:
  dist += loga - logb
  a = a >> (loga - logb)
 else:
  b = b >> (logb - loga)
  dist += logb - loga
 #print a, b
 
 x = a ^ b
 if x:
  dist += (int(math.log(x, 2)) + 1) * 2;
 
 print(dist)
 #print "   "


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)
 


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))

 #print a, b, loga, logb
 
 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
  else:
   if (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)
  
  
  #print( resolve2(nodes) )

__starting_point()

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 = int(math.floor(_max / 2))
  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
  else:
   if (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] = int ( math.floor(nodes[0] /( 2**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)
  
  
  #print( resolve2(nodes) )

__starting_point()