Question
Number Dance
Lila holds two positive integers A and B. Her task is to repeat this process until A becomes 0:
Find the final value of B after all steps.
- If A > B, swap A and B.
- Otherwise, update A to (B − A) and set B to the old value of A.
Find the final value of B after all steps.
Input
The first line of input will contain a single integer T, denoting the number of test cases.
Each test case consists of one line of input, two space-separated integers A and B.
Constraints
1 ≤ T ≤ 105
1 ≤ A, B ≤ 109
Each test case consists of one line of input, two space-separated integers A and B.
Constraints
1 ≤ T ≤ 105
1 ≤ A, B ≤ 109
Output
For each test case, output on a new line, the final value of B after all operations.
Example
Sample Input
3
2 5
6 3
2 10
Sample Output
1
3
2
Explanation
The sequence of operations is as follows:
- A = 2, B = 5: Set A = 5 - 2 = 3 and B = 2;
- A = 3, B = 2: Swap X and Y
- A = 2, B = 3: Set A = 3 - 2 = 1 and B = 2;
- A = 1, B = 2: Set A = 2 - 1 = 1 and B = 1;
- A = 1, B = 1: Set A = 1 - 1 = 0, B = 1;
3
2 5
6 3
2 10
Sample Output
1
3
2
Explanation
The sequence of operations is as follows:
- A = 2, B = 5: Set A = 5 - 2 = 3 and B = 2;
- A = 3, B = 2: Swap X and Y
- A = 2, B = 3: Set A = 3 - 2 = 1 and B = 2;
- A = 1, B = 2: Set A = 2 - 1 = 1 and B = 1;
- A = 1, B = 1: Set A = 1 - 1 = 0, B = 1;