There is an interesting game. We start with a number K
. Then three operations is allowed:
1. Multiply current number by 2
2. Divide current number by 2, if current number is even.
3. Increase current number by 1
Our target is to get number P
with minimum operations. You can assume 0 < P,K
< 100000, and the number can not be greater than or equal to 100000 at any time.
The first line is an integer T
, the number of test cases. Then T
Each test case contain two numbers K
in one line separated by a space.
Output the minimum number of operations. If it is impossible to get P
, output -1 instead.
For the first sample, the operation is 11 -> 12 -> 6 -> 3 -> 4 -> 5 -> 10 -> 20.
For the second sample, even though we can get 99999 -> 100000 -> 50000, but the number is not allowed to be greater than or equal to 100000.