Add or multiple

Add or multiple

Time Limit: 2.0 s

Memory Limit: 256.0 MB

Description

Now a days, Shakib is only thinking about addition and multiplication. His friend Roy prepared a problem to check his thinking ablity on addition and multiplication. The problem is very simple,

You are given two inetegers \(A\) and \(B\) (\(A<=B\)) and you need to find out minimum number of operations requried to make \(A\) equal to \(B\).

In one operations you can do one of the following
\(A = A + 1\) (increase A by 1)
or
\(A = A * 2\) (multiply A by 2)

Unfortunately, Shakib is visiting his village and we don't want to distrub him. Instead of Shakib, can you solve it.

Input

First line of input takes an integer \(T\) : number of testcases
Each testcase takes two integers \(A,B\)

\(1 <= T <= 10^5\)
\(1 <= A,B <= 10^9\)

Output

Print one integer in each of \(T\) lines: minimum operation to make A equal to B

Sample

Input Output
3
1 8
3 3
2 5
3
0
2

In the first test case, one of the optimal way we can get 8,

1st operation : multiple by 2, A = A * 2, A = 2;

second operation : multiple by 2, A = A * 2, A = 4;

third operation : multiple by 2, A = A * 2, A = 8;

After third operation, A is equal to B, so the answer is 3.

In the second test case, A is already equal to B. so we don't need any operations.

In the third test case ,

1st operation : multiple A by 2, A = A * 2, A = 4;

second operation : increase A by 1, A = A + 1, A = 5;

Only 2 operations are needed to make A equal to B, so the answer is 2.

Information

ID
1044
Difficulty
7
Category
Beginners | Math Click to Show
Tags
# Submissions
78
Accepted
16
Accepted Ratio
21%
Uploaded By

Related

In following contests:

TLE_Headquarters - round #1