Largest Square Tiling

In this problem, you are given a rectangle with dimensions (W \times H). Your task is to find the side length (s) of the largest square that can exactly tile the rectangle without any leftover space. It is known from number theory that the side length (s) is given by (s = \gcd(W, H)), where (\gcd(\cdot, \cdot)) denotes the greatest common divisor.

inputFormat

The input begins with an integer (T) representing the number of test cases. Each of the next (T) lines contains two space-separated integers (W) and (H) indicating the width and height of the rectangle respectively.

outputFormat

For each test case, output the side length of the largest square that can exactly tile the rectangle on a new line.## sample

3
6 9
15 25
100 45

3
5
5