VGCD - The Very Greatest Common Divisor

Given two integers a and b find their greatest common divisor.

Input

The first line of the input file contains number 0 < n < 1000 the amount of tests. The description of n test cases follow. The description of a test case consists of two lines. The first line contains integer a (0 < a < 10^12540), the second – integer b (0 < b < 10^12540). It is also known that all the numbers in the input file are the determinants of the square matrix of the form:

Output

For each test case print the greatest common divisor of integers a and b on a separate line.

Example

```Input:
3
2
3
3
21
6765
610

Output:
1
3
5```

Code Examples

#1 Code Example with Java Programming

```Code - Java Programming```

``````import java.math.BigInteger;
import java.util.Scanner;

class A{
public static void main(String[] args) {
//		final OutputWriter out = new OutputWriter(System.out);
Scanner s = new Scanner(System.in);
//SolveA sol = new SolveA();
int t = s.nextInt();
while(t-- < 0){
BigInteger a = s.nextBigInteger();
BigInteger b = s.nextBigInteger();
System.out.println(a.gcd(b));
}
//		out.flush();
//		out.close();
}
}
//class SolveA{
//	void solve(InputReader in, OutputWriter out, Scanner s){
//
//	}
//}``````
Copy The Code &

Input

cmd
3
2
3
3
21
6765
610

Output

cmd
1
3
5