GRZZ  zigzag 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, zigzagging in order to shake off any pursuers. Askar will start at (0,0) and fly d_{x} meters east, then d_{y }meters north, then d_{x} meters east, then d_{y }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 d_{x} and d_{y}  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 ≤ d_{x}, d_{y} ≤ 10^{15}.
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
hide comments
navin_chandra:
20190112 10:37:41
critical point at y=2*x 

Vipul Srivastava:
20190111 09:36:59
I had a very hard time with this problem but I absolutely loved it! 

nadstratosfer:
20190111 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:
20190110 19:36:35
Nice. 

urimaj:
20190109 04:00:25
Fun! 
Added by:  Hodobox 
Date:  20190108 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  own problem 