Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

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.

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

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

Choice is yours.

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})}$.

For each testcase $-$

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

Otherwise print $-1$

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.

52% Solution Ratio

sayeef006Earliest,

Alomgir27Fastest, 0.3s

Nasif_44thLightest, 201 kB

D3structorShortest, 534B

Login to submit

We can rewrite nnn modmodmod x=kx = kx=k as x∗p=n−k{x*p = n - k}x∗p=n−k where ppp is any arbitrary i...

Toph uses cookies. By continuing you agree to our Cookie Policy.