Question
Sub or Swp
Output the final value of Y after all operations.
You are given two positive integers X and Y. Repeat the following operation until X is not 0:
- If X > Y, swap X and Y;
- Otherwise, set X = (Y − X) and Y = X.
Output the final value of Y after all operations.
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 X and Y.
Constraints
1 ≤ T ≤ 105
1 ≤ X, Y ≤ 109
Each test case consists of one line of input, two space-separated integers X and Y.
Constraints
1 ≤ T ≤ 105
1 ≤ X, Y ≤ 109
Output
For each test case, output on a new line, the final value of Y 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:
- X = 2, Y = 5: Set X = 5 - 2 = 3 and Y = 2;
- X = 3, Y = 2: Swap X and Y
- X = 2, Y = 3: Set X = 3 - 2 = 1 and Y = 2;
- X = 1, Y = 2: Set X = 2 - 1 = 1 and Y = 1;
- X = 1, Y = 1: Set X = 1 - 1 = 0, Y = 1;
3
2 5
6 3
2 10
Sample Output
1
3
2
Explanation
The sequence of operations is as follows:
- X = 2, Y = 5: Set X = 5 - 2 = 3 and Y = 2;
- X = 3, Y = 2: Swap X and Y
- X = 2, Y = 3: Set X = 3 - 2 = 1 and Y = 2;
- X = 1, Y = 2: Set X = 2 - 1 = 1 and Y = 1;
- X = 1, Y = 1: Set X = 1 - 1 = 0, Y = 1;