GRZZ - zig-zag on the golden river

no tags 

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


hide comments
navin_chandra: 2019-01-12 10:37:41

critical point at y=2*x

Vipul Srivastava: 2019-01-11 09:36:59

I had a very hard time with this problem but I absolutely loved it!

nadstratosfer: 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!

julkas: 2019-01-10 19:36:35

Nice.

urimaj: 2019-01-09 04:00:25

Fun!


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