Practice on Toph

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

Choice Is Yours

By rifatrraazz · Limits 1s, 512 MB

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 nn and kk, find such x,yx,y (y>x)(y > x) that -

  • nn modmod xx == kk

  • nn modmod yy == kk

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

If such x,yx,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, tt(1t1000){(1 \le t \le 1000)}-number of test cases.

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

Output

For each testcase -

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

  • Otherwise print 1-1

Sample

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

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

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

Discussion

Statistics


52% Solution Ratio

sayeef006Earliest, 2M ago

Alomgir27Fastest, 0.3s

Nasif_44thLightest, 201 kB

D3structorShortest, 534B

Submit

Login to submit

Editorial

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...

Related Contests

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