14041404 SUSTech Online Judge
Problem 1404 --Space Traveling

1404: Space Traveling

Time Limit: 3 Sec  Memory Limit: 256 MB
Submit: 261  Solved: 126
[Submit][Status][Web Board]


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.


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. 


\(T\) lines, each contains an integer, indicating the number of portals you need to travel.

Sample Input

2 3

Sample Output