You are given three numbers N, a, b. You can build a number X by repeating N 'a' times and the number Y by repeating N 'b' times. Now that you have the numbers X and Y, determine the GCD of the two numbers X and Y.

Input format:

The first line contains an integer T, the number of test cases.

Then for each test case, there are three integers in each line: N, a, b.

Output format:

Print the required answer for each test case in a single line.

Constraints:

1 <= T <= 100

1 <= N, a, b <= 10^18

Sample:

Input:
1
123 2 3

Output:
123