Doctor Strange has hidden Time Stone inside a box . You have to relocate the stone to a new place . The box can be opened by solving a math puzzle called Strange GCD . In mathematics, GCD is the greatest common divisor, and it's an easy task to calculate the GCD between two positive integers. A common divisor for two positive numbers is a number which both numbers are divisible by.
In Strange GCD you have to find the greatest common divisor d of two integers a and b that is in a given range from low to high (inclusive), i.e. low ≤ d ≤ high. It is possible that there is no common divisor in the given range.
You will be given the four integers a, b, low and high.
Input
The first line contains the number of test cases t.
Each of the next t lines contain four integers a, b, low and high.
Constraints
1 ≤ t ≤ 10^3.
1 ≤ a, b ≤ 10^9.
1 ≤ low,high ≤ 10^9.
Output
Print t lines. The t-th of them should contain the result of the t-th input. If there is no common divisor in the given range for any case, you should print -1 as a result for that case.
In 1st test case, 3 is the highest number that lies in range [1,5] and is common divisor of 9 and 27.
In 2nd test case , there are no common divisors of 9 and 27 lying in [10,11]
In 3rd case , 5 is highest number satisfying the required conditions.
