Consider a full binary tree with an infinite number of levels. The vertices are labeled with positive integers, starting from the root and moving down the tree, from left to right on each level. In the example below you can see the first 444 levels of the tree:
123456789101112131415
Answer qqq (1≤q≤106)(1 \leq q \leq 10^6)(1≤q≤106) queries of the form: find the minimum distance between vertices aaa and bbb (1≤a,b≤1018)(1 \leq a, b \leq 10^{18})(1≤a,b≤1018).
The first line contains integer qqq.
The next qqq lines contain two integers, aaa and bbb.
Print qqq lines, on line iii the answer for the ithi^{th}ith query.
- 1≤q≤1061 \leq q \leq 10^61≤q≤106
- 1≤a,b≤10181 \leq a, b \leq 10^{18}1≤a,b≤1018
| Input | Output |
|---|---|
4 1 1 1 2 2 3 10 6 | 0 1 2 5 |