7367: CodeChef BINTREE - Shortest Path in Binary Trees
[Creator : ]
Description
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$
$1 ≤ i,j ≤ 10^9$
Sample 1 Input
3
1 2
2 3
4 3
Sample 1 Output
1
2
3
For first query, 1 is directly connected to 2 by an edge. Hence distance 1.