Professor X likes the class to be interactive! Hence, now and then, he calls out a random roll number by his intuition and the student whose roll number is called out has to explain the answer to the problem. A number with more Intuitiveness is more likely to be called out. However, considering the professor's previous patterns of calling out roll numbers, the students can accurately guess the range in which the called roll number will lie. Your task is to find the roll number which is least likely to be called out i.e. the number with least Intuitiveness in that range.
Intuitiveness of a natural number N is the ratio of sum of all its proper divisors to the number itself. Thus, for example, the Intuitiveness of natural number 8 is 0.875 = (1 + 2 + 4)/8 and the Intuitiveness of 6 is 1 = (1 + 2 + 3)/6. Proper divisor of a number is a divisor which is strictly less than the number. Write a program which will find the number with least Intuitiveness in the given range.

Input:
The first line contains the number of test cases T. Each of the next T lines contains two space separated integers A and B.

Output:
For each test case, output on a separate line, an integer N such that A ≤ N ≤ and N has least Intuitiveness. If there is more than one such number, output the one with least magnitude.

Constraints:

• 1 ≤ T ≤ 10
• 1 ≤ A ≤ B ≤ 1000000