Problem 1404 --Space Traveling1404: Space Traveling
Time Limit: 3 Sec Memory Limit: 256 MB
Submit: 261 Solved: 126
[Submit][Status][Web Board]Description
In the 22nd century, interstellar travel has become part of our daily life. The universe can be treated as a complete binary tree, and every planet is a node. Each planet (starting from planet 1) \(i\) is connected with \(2 i\) and \(2 i + 1\) through portals. Assuming you are in planet \(x\), and you need to go to planet \(y\) to reunion with your family. You need to know how many portals you need to travel through to reach planet \(y\), so that you can prepare your spaceship in advance to prevent it from breaking down in the middle of nowhere.
Input
The first line contain an integer \(T(1 \leq T \leq 10^6)\), indicating the number of test cases.
In the next \(T\) lines, each line contains wo integers \(x(1 \leq x \leq 10^{18})\), \(y(1 \leq y \leq 10^{18})\), as described above.
Output
\(T\) lines, each contains an integer, indicating the number of portals you need to travel.
Sample Input
1
2 3
Sample Output
2
HINT
Source
[Submit][Status]