Description
The description provided for this problem:
Agent Ω used the information she decrypted in the messages to locate a vault that the Serpent is using to store blackmail material on other politicians. Now she just needs to break into it, possibly through a series of valut doors.
For a given door, each bolt in the safe is in either an “up” or “down” position. Agent Ω knows both the starting state of the bolts and the target state that she needs to reach to open the valut door. Each of these states she represents as a binary value where a one represents an up-bolt, and a 0 represents a down-bolt.
The start state is always represented by a higher value that the target state, which is good, since Agent Ω has only figured out how to reduce the value represented. In fact, she can only reduce the value by powers of two. So she could adjust bolts to reduce the value by 1, 2, 4, 8, 16, or 32, but NOT 5 or 20 (or any other non-power-of-two).
Given a starting position value (N) and a goal value (G), can you figure out the fewest number of adjustments it would take to reach the target and open the vault?
Input Format
The first line will contain a value T indicating the number of vault doors (the number of test cases).
The next T lines will each contain two integers N, indicating the starting value of the lock, and G, the goal value.
Constraints
1 ≤ T ≤ 200,000
0 ≤ G ≤ N ≤ 264 – 1
Output Format
N lines, each indicating the number of adjustments it would take to open the vault.
Example 0
Sample Input
1
12 1
Sample Output
3
Explanation
There is a single vault door starting at a value of 12, which needs to be dropped to a value f 1 to open. Three adjustments are needed:
The first adjustment reduces the value by 8, since 8 (23) is the largest power of two less than 12. This leaves a value of four.
Four is a power of two, but we must target a value of one, so shifting by four would overshoot that. So the second adjustment reduces it by 2 (21).
The third and final adjustment reduces it by 1 (20) to the target of 1.
