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

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

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

Constraints

1 ≤ T ≤ 100

1 ≤ N, a, b ≤ 10¹⁸

Sample

Input:
1
123 2 3

Output:
123