G. The last Bit bender
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ahmad has expanded his repertoire from strings to bits! Naturally, he only knows one spell: transforming an integer $$$x$$$ into $$$F(x)$$$.

The function $$$F(x)$$$ changes the rightmost zero (the least significant unset bit) in the binary representation of $$$x$$$ into a $$$1$$$.

For example:

- $$$F(5) = F(101_2) = 111_2 = 7$$$

- $$$F(7) = F(0111_2) = 1111_2 = 15$$$

- $$$F(0) = F(0_2) = 1_2 = 1$$$

- $$$F(2) = F(10_2) = 11_2 = 3$$$

You are given two positive integers $$$a$$$ and $$$b$$$. In a single operation, you may apply Ahmad's spell to either $$$a$$$ or $$$b$$$, replacing the chosen number with $$$F(a)$$$ or $$$F(b)$$$, respectively. You may perform this operation as many times as you like.

Find the minimum total number of spells required to make $$$a = b$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Each of the next $$$t$$$ lines contains two integers $$$a$$$ and $$$b$$$ ($$$1 \le a,b \le 10^{18}$$$).

Output

For each test case, output one integer — the minimum number of moves required to make $$$a=b$$$.

Example
Input
6
5 7
42 42
4 8
1 2
10 12
15 16
Output
1
0
6
2
4
5