Magic Bits

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

Consider two integers, X and Y. There are two operations which you can perform any number of times:

  • Set X to X+1.
  • Set X to X OR Y.

For each of the T test cases, you must calculate the fewest operations needed to make X equal to Y or determine that no such sequence of operations exists.


1 \le T \le 10^6

0 \le X, Y < 2^{60}

Subtask 1 [30%]

T = 1

0 \le X, Y \le 10^6

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line contains an integer, T, the number of test cases.

Each of the next T lines contains two space-separated integers, X and Y.

Output Specification

For each test case, on its own line, output the fewest operations needed to make X equal to Y. If no sequence of operations exists, output -1 instead.

Sample Input

1 2
3 6

Sample Output

Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported


There are no comments at the moment.