It's Valentine Time . Love is in Air . So, Mr. Pole is looking for bride . For becoming his bride , there is only one criteria. She should be expert in Coding . So, Mr.Pole has given a question for 1st Elimination round :

Given a range L and R , you have to tell the number between L and R such that difference between no. of divisors and prime divisors is maximum. If two number has same difference , print the smallest one .

Input : First line contains T , denoting number of Test cases Next T lines contains L and R denoting the range for the query.

Output : Print the desired result in each line.

Constraints :

1<=T<=10

1<=L<=R<=10^6

AUTHOR : trico