Background

Next to a small grove stands a fantasy castle. This is the land of Country E, and Little E is the king of Country E.

Now, the great king of Country E is putting on armor and going to war.

However, it is said that the king of Country E met two people called ACCEPT and BOTH. Who are they?

Problem Description

Given a positive integer $n$, you can perform the following operations:

• "ACCEPT". Pay a cost of $1$ to bitwise OR the binary form of $n$ with a positive integer.
• "BOTH". Pay a cost of $1$ to bitwise AND the binary form of $n$ with a positive integer.

Both operations can be used multiple times (or not used at all). Please find the minimum cost to transform $n$ into $m$.

Help: What are bitwise AND and bitwise OR

Input Format

This problem has multiple test cases.

The first line contains a positive integer $T$, indicating the number of test cases.

The next $T$ lines each contain two positive integers $n, m$, separated by spaces.

Output Format

Output $T$ lines. Each line contains one integer, which is the answer.

3
1 1
4 5
1 4

0
1
2

Hint

Sample Explanation

• For $n = 1$ and $m = 1$, no operation is needed.
• For $n = 4$ and $m = 5$, one feasible plan is to use "ACCEPT $1$".
• For $n = 1$ and $m = 4$, one feasible plan is to use "ACCEPT $998{,}244{,}853$" and then "BOTH $14$" in order.

Constraints

This problem uses bundled tests.

For all testdata, $1 \le T \le 2 \times 10^5$ and $1 \le n, m \le 10^{18}$.

Translated by ChatGPT 5