Largest Square Flower Bed

You are given the dimensions of a rectangular garden with length L and width W. Your task is to determine the side length of the largest possible square flower bed that can be completely contained within the garden. The side length of the square must be a divisor of both L and W. Mathematically, the side length is given by the greatest common divisor (GCD) of L and W. In other words, find the largest integer S such that:

\( S = \gcd(L, W) \)

Note: All operations and calculations must be performed using integer arithmetic.

inputFormat

The first line contains a single integer T, the number of test cases. Each of the next T lines contains two space separated integers L and W denoting the dimensions of the garden.

Constraints:

• 1 ≤ T ≤ 10⁵
• 1 ≤ L, W ≤ 10⁹

outputFormat

For each test case, output a single line containing the side length of the largest square flower bed that can fit into the rectangular garden.

## sample

6
12 8
5 5
15 25
1000000000 999999999
48 18
1000000000 500000000

4
5
5
1
6
500000000

</p>