B. Bessie And Rounding
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Bessie is trying to convert a number $$$X$$$ to $$$Y$$$.

In one operation, Bessie can choose an integer $$$M$$$ ($$$M \ge 1$$$) and round $$$X$$$ to the nearest multiple of $$$M$$$. If $$$X$$$ is exactly in the middle of two multiples of $$$M$$$, it is rounded up. Note that $$$0$$$ is a multiple of every number.

What is the least number of operations Bessie needs to perform to convert $$$X$$$ to $$$Y$$$? Output this number, or $$$-1$$$ if it is impossible.

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^4$$$) — the number of test cases.

Each of the next $$$T$$$ lines contains two integers $$$X$$$ and $$$Y$$$ ($$$1 \le X, Y \le 10^9$$$) — the initial number and the target number.

Output

For each test case, output a single integer — the minimum number of operations required, or $$$-1$$$ if it is impossible.

Examples
Input
5
2 5
6 4
4 1
3 3
1 10
Output
2
2
-1
0
4
Input
7
1 1000000000
999999999 1
999999999 10
999999999 11
999999999 12
999999999 13
1000000000 100
Output
30
-1
46
46
46
46
40
Note

In the first testcase of the first sample, $$$X=2$$$ and $$$Y=5$$$. Bessie can perform the following $$$2$$$ operations:

  • Choose $$$M=4$$$. The multiples of $$$4$$$ are $$$0, 4, 8, \dots$$$. $$$X=2$$$ is exactly in the middle of $$$0$$$ and $$$4$$$, so it rounds up to $$$4$$$. Now $$$X=4$$$.
  • Choose $$$M=5$$$. The multiples of $$$5$$$ are $$$0, 5, 10, \dots$$$. The nearest multiple to $$$4$$$ is $$$5$$$. Now $$$X=5$$$.

It can be proven that it is impossible to do this in fewer than $$$2$$$ operations.

In the second testcase of the first sample, $$$X=6$$$ and $$$Y=4$$$.

  • Choose $$$M=5$$$. $$$X=6$$$ is nearest to $$$5$$$. Now $$$X=5$$$.
  • Choose $$$M=4$$$. $$$X=5$$$ is nearest to $$$4$$$. Now $$$X=4$$$.

It can be proven that it is impossible to do this in fewer than $$$2$$$ operations.