Limak is a little bear who loves school. Today was his first lesson in cryptography, and the teacher assigned some difficult homework—to find any number with exactly divisors. Limak wants to go the extra mile and find the biggest possible number; however, his teacher explained that there are arbitrarily large numbers with this property.
To give this little bear a more achievable challenge, the teacher advised him to consider only numbers not greater than .
Given and , what is the largest number Limak can find?
Input Format
The first line contains an integer, (the number of test cases).
The subsequent lines of test cases each contain two space-separated integers, and , respectively.
Constraints
Output Format
For each test case, print the biggest number Limak can find on a new line. Print if no such number exists.
Sample Input
3
15 3
15 4
15 5
Sample Output
9
15
-1
Explanation
As each test case uses , here are the numbers ranging from to and their divisors:
is evenly divisible by numbers (, , , and ).
is evenly divisible by numbers (, , , and ).
is evenly divisible by numbers ( and ).
is evenly divisible by numbers (, , , , , and ).
is evenly divisible by numbers ( and ).
is evenly divisible by numbers (, , , and ).
is evenly divisible by numbers (, , and ).
is evenly divisible by numbers (, , , and ).
is evenly divisible by numbers ( and ).
is evenly divisible by numbers (, , and ).
is evenly divisible by numbers ( and ).
is evenly divisible by numbers (, , and ).
is evenly divisible by numbers ( and ).
is evenly divisible by numbers ( and ).
is only evenly divisible by number ().
Test Case 0:
We must find the largest number having exactly divisors. Because is the largest number having exactly divisors, we print on a new line.
Test Case 1:
We must find the largest number having exactly divisors. Because is the largest number in the list above having exactly divisors, we print on a new line.
Test Case 2:
There is no number between and having exactly divisors, so we print on a new line.