Largest Square Tiling

Given a rectangular field of dimensions \(m \times n\), your task is to determine the side length of the largest square that can completely tile the field without any leftovers. This problem can be solved by finding the greatest common divisor (\(\gcd(m, n)\)) of its dimensions, as the side length of the largest square is exactly \(\gcd(m, n)\).

For example, if the dimensions are 15 and 20, then the largest possible square will have a side length of 5 because \(\gcd(15, 20) = 5\).

inputFormat

The input begins with an integer \(t\) denoting the number of test cases. Each of the following \(t\) lines contains two space-separated integers \(m\) and \(n\), representing the dimensions of the field.

outputFormat

For each test case, output a single line that contains an integer which is the side length of the largest square that can tile the field. This number is equal to \(\gcd(m, n)\).

3
15 20
40 60
7 3

5
20
1