While learning about binary operations, Little H encountered a classic problem: given an integer initially at 0, each operation consists of multiplying it by 2 or adding 1. Find the minimum number of operations to transform it into a given positive integer $x$. Little H discovered that this can be solved using the binary representation of $x$.

Based on this problem, Little H proposed the following: given two positive integers $x$ and $y$, define one operation as one of the following four types: 1. Multiply $x$ by 2, i.e., $x \leftarrow 2x$; 2. Multiply $y$ by 2, i.e., $y \leftarrow 2y$; 3. Add 1 to $x$, i.e., $x \leftarrow x + 1$; 4. Add 1 to $y$, i.e., $y \leftarrow y + 1$.

Little H wants to know the minimum number of operations required to make $x$ and $y$ equal. You need to help Little H find the minimum number of operations.

Implementation Details

You do not need to, and should not, implement the main function.

You must ensure that your submitted program includes the header file binary.h by adding the following code at the beginning of your program:

#include "binary.h"

You must implement the following two functions in your submitted source file binary.cpp:

void init(int c, int t);

• $c$ and $t$ represent the test case ID and the number of test groups, respectively. $c = 0$ indicates that the test case is a sample.
• For each test case, this function will be called exactly once by the interactor when the program starts.

long long binary(long long x, long long y);

• $x$ and $y$ represent the two given numbers.
• This function must return the minimum number of operations.
• For each test case, this function will be called exactly $t$ times by the interactor.

Note: In any case, the execution time of the interactor will not exceed 1.8 seconds, and the memory used is fixed and does not exceed 64 MiB.

Testing Your Program

The grader.cpp provided in the problem directory is a reference implementation of the interactor. The interactor used for final testing will differ from this reference implementation, so your solution should not rely on the specific implementation of the interactor.

You can compile your program using the following command in the problem directory:

g++ grader.cpp binary.cpp -o binary -O2 -std=c++14 -static

For the resulting executable: It reads data from standard input in the following format: The first line contains two non-negative integers $c, t$, representing the test case ID and the number of test groups. The following lines contain the test data for each group: The first line contains two positive integers $x, y$, representing the given numbers. It outputs data to standard output in the following format: For each test group, output one integer per line, representing the minimum number of operations.

File Explanation

In the problem directory: 1. grader.cpp is the provided reference implementation of the interactor. 2. binary.h is the header file; you do not need to concern yourself with its contents. 3. template_binary.cpp is the provided sample code, which you may refer to when implementing your own code.

Please ensure you back up all provided files. During final evaluation, only the binary.cpp file in the problem directory will be tested; modifications to files other than this one will not affect the evaluation results.

Examples

Input 1

0 5
1 2
1 5
3 6
7 33
5 9

Output 1

1
3
1
4
2

Data Range

For all test data: $1 \le t \le 5 \times 10^7$ $1 \le x < y \le 10^{18}$

Special Property A: $y - x \le 10^3$. Special Property B: There exist $k \ge 1$ and $0 \le z < 2^k$ such that $y = x \times 2^k + z$.

Scoring

Note: Participants should not attempt to obtain internal information about the interactor through illegal means, such as directly interacting with standard input/output streams. Such behavior will be considered cheating. The final evaluation interactor differs from the sample interactor.

This problem is subject to the same constraints as traditional problems; for example, compilation errors will result in 0 points for the entire problem, and runtime errors, time limit exceeded, or memory limit exceeded will result in 0 points for the corresponding test cases. Participants may only access variables defined within their own program and variables provided by the interactor; attempting to access other memory addresses may lead to compilation or runtime errors.

Based on the above conditions: * For each test case, the program receives full marks if and only if the answer returned by the binary function is correct for every call.