Greatest Common Divisor Calculation

This problem requires you to compute the greatest common divisor (GCD) for a list of pairs of integers. For each pair (a, b), the GCD is the largest positive integer that divides both a and b without leaving a remainder.

You will be given an integer n denoting the number of pairs followed by n lines, each containing two integers. Your task is to compute and print the GCD for each pair on a separate line.

Note: Use the standard algorithm for computing the GCD (e.g. the Euclidean algorithm).

inputFormat

The first line of input contains a single integer n (1 ≤ n ≤ 10^5) representing the number of pairs. Each of the next n lines contains two integers a and b (1 ≤ a, b ≤ 10^9) separated by a space.

outputFormat

Output n lines. The i-th line should contain the greatest common divisor of a and b from the i-th input pair.## sample

3
15 25
25 30
17 19

5
5
1