SPEED - Circular Track

no tags 

Two persons are running on a circular track either in the same direction or in the opposite direction, indefinitely. The speed of both of them is given to you. Speed will be positive in clockwise direction, and negative in anticlockwise direction. Print the number of distinct points, at which they will meet on the circle.

Input

First line contains T, number of test cases. Each test case contains two integers, S1 and S2 (not equal to zero) which are the speeds of the two persons. S1 and S2 will be distinct.

Edited: All the numbers fit in signed 32-bit integer.

Output

Print in a separate line, the number of distinct points at which they meet.

Example

Input
2
1 2
1 -1

Output
1
2

hide comments
sushantoberoi3: 2016-10-31 07:04:50

good question!!

vineetpratik: 2016-07-01 17:04:03

Hint 1: you have to find distinct points at which they both meet(after some time those points keep on repeating but number of distinct points is finite)
Hint 2: gcd and relative motion can help

dwij28: 2015-12-26 01:37:21

Test cases are relatively weak. My highly UN-optimised / slow code gave 0.0 seconds..

darkhire21: 2015-10-26 19:33:00

don't mention hint in comments ...!!

impossible_1: 2015-09-24 08:12:26

euclidean algorithm of gcd .......then easy.

shubham agrawal: 2015-08-15 12:55:51

xpshekhar..
s1 and s2 will be distinct always..
read carefully..
at (0,2)
output will be 1

xpshekhar: 2015-08-11 22:48:43

can anyone please tell what will be output at (1,1) or (0,2)

MishThi: 2015-08-05 22:45:16

Nice concept. :P

anuveshkothari: 2015-07-26 17:27:49

you have to find all the distinct points where they can meet until they meet again at starting point after some time..
in java..
with Scanner - 0.09
with BufferedReader - 0.05

Last edit: 2015-07-26 17:53:04
SangKuan: 2015-07-02 07:33:04

nice math


Added by:Nikunj Jain
Date:2011-07-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All