The inhabitants of this world live in a city with an infinite number of houses. Each house has a unique positive integer identifier $n$. The streets of this city are constructed as follows: for any house $n$, there is exactly one street connecting it to a house with a larger identifier, which is $n + \mathrm{lowbit}(n)$.

The function $\mathrm{lowbit}(n)$ is defined as the value obtained by keeping only the lowest set bit in the binary representation of $n$. A convenient bitwise method to calculate this is lowbit(n) = n & -n.

It can be proven that any two houses can reach each other via these bidirectional roads. Your task is to process several queries to calculate the shortest path between two houses, where each edge traversed counts as one unit of length.

Input

The first line contains an integer $q$, representing the number of queries.

Each of the next $q$ lines contains two positive integers $x$ and $y$, representing the two houses in the query.

Output

Output $q$ lines, each containing an integer representing the length of the shortest path.

Examples

Input 1

2
1 3
2 4

Output 1

3
1

Subtasks

For $20\%$ of the data, it is guaranteed that $1 \leq q \leq 10$, $1 \le x,y \le 2^{3}$.

For $30\%$ of the data, it is guaranteed that $1 \leq q \leq 500$, $1 \le x,y \le 2^{9}$.

For $70\%$ of the data, it is guaranteed that $1 \leq q \leq 10^5$, $1 \le x,y \le 2^{20}$.

For $100\%$ of the data, it is guaranteed that $1 \leq q \leq 3 \times 10^5$, $1 \le x, y \le 2^{60}$.