The Very Greatest Common Divisor
Medium
Execution time limit is 2 seconds
Runtime memory usage limit is 64 megabytes
You need to find greatest common divisor of two integers a and b. Each number a and b are determinants of the square matrix of the form:
Input
The first line of the input file contains number n < 250 of test cases. 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).
Output
For each test case print the greatest common divisor of integers a and b on a separate line.
Examples
Input #1
Answer #1
Submissions 218
Acceptance rate 11%