Choice Is Yours

For not participating on contests regularly, Hasnaine (read Has9) has decided to kill Santo. But nobody wants to die. Santo too. So all he wants is a second chance. We all know that Has9 is a very kind person. So he gives Santo the following problem. If Santo can solve it, Has9 will forgive him (of course Santo has to commit not to miss any contests further).

For given $n$ and $k$, find such $x,y$ $(y > x)$ that $-$

• $n$ $mod$ $x$ $=$ $k$

• $n$ $mod$ $y$ $=$ $k$

• $gcd(x, y)$ is maximum.

If such $x,y$ doesn’t exist, report it.

After trying a thousand times, Santo couldn't solve it as he did not practice for a long time. So, for the first time, Santo has decided to cheat to save his life. If you solve this problem, Santo will copy the solution and show it to Has9. At this moment, you have two choices.

1. Solve this problem, save Santo and increase your rank in the standings.

2. Do not solve, let Santo die and indirectly kill Has9 (of course Law will execute Has9 for killing Santo).

Choice is yours.

Input

First line of the input is an integer, $t$${(1 \le t \le 1000)}$$-$number of test cases.

Each testcase contains two integers, $n, k$${(0 \le k < n \le 10^{12})}$.

Output

For each testcase $-$

• If such $x,y$ exists, print $gcd(x,y)$

• Otherwise print $-1$

Sample

Input	Output
4 15 3 12 2 180 12 30 21	6 5 84 -1

If you don’t know what is $mod$, learn it.

If you don’t know what is $gcd$, learn it.