GRZZ - zig-zag on the golden river

Askar is planning to steal some gold from the golden river of Slovakistan! The river forms at (0,0) and flows in the north east direction - the line y = x.

The river is well protected by the king's army, which is sure to give chase after him. As such, he came up with an ingenious plan - he will fly a helicopter, zig-zagging in order to shake off any pursuers. Askar will start at (0,0) and fly dx meters east, then dy meters north, then dx meters east, then dy meters north, ... forever.

Of course, he will only have a small window of opportunity to extract some gold from the river every time he crosses (or touches) it. He has yet to decide the exact values of dx and dy - some might give him better chances at a successful escape, others will allow him to grab more loot.

Help Askar and tell him how much he can get away with for each plan.

Input

The first line contains an integer 1 ≤ T ≤ 1000 - the number of plans.

T lines follow, each containing two integers 1 ≤ dx, dy ≤ 1015.

Output

Output a single integer - the number of times Askar would cross the golden river.

If Askar crosses the river an infinite number of times, output -1 instead.

Example

Input:
2
1 1
3 2 Output: -1
1

Sample depictions


Added by:Hodobox
Date:2019-01-08
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:own problem

hide comments
2019-09-03 19:18:59 Tushar Makkar (Retired)
@Hodobox: Can you provide a sample where my solution isn't working fine? I tried and tested a lot of sample examples and it was working fine on all of them.

RE: You seem to be having precision issues. You fail only for some very large inputs.

RE: Thanks for the reply. The issue was in the way Python2.7 does integral division.

Last edit: 2019-09-05 06:54:25
2019-01-12 10:37:41
critical point at y=2*x
2019-01-11 09:36:59 Vipul Srivastava
I had a very hard time with this problem but I absolutely loved it!
2019-01-11 03:04:02
Hodobox sets the kind of problems where "AC in 1 go!!!1" actually stands for something. Always remember, a few hours of trial and error can save you many minutes of writing a robust tester!
2019-01-10 19:36:35
Nice.
2019-01-09 04:00:25
Fun!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.