ABA12A - Help Balaji!

Balaji was reading number theory. When reading about primes, he was thinking about numbers which could be expressed as a product of primes. He wanted to know the largest number in a range which could be expressed as a product of primes. Balaji’s maths teacher is not so good at maths and so he was taught that 1 is prime. You, being a good programmer, help him with the task.

Input

The first line of input consists of C, the number of test cases, followed by C lines containing two space separated numbers a and b, the first and last number in the range (inclusive).

1 < C < 100

0 < A < B < 1e12

0 < B - A < 1e6

Output

For each test case, print a single line containing the largest number which can be represented as a product of primes, considering 1 to be prime.

Example

Input:
1
1 4

Output:
4

Explanation of Test Case

4 can be expressed as 2 × 2.


Added by:Kashyap Krishnakumar
Date:2012-01-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem

hide comments
2018-10-12 23:14:07
Can it be solved using miller rabin test?
or did anyone use segment sieves?
2016-10-26 18:44:51 sharif ullah
সবাই মজা নেয় (Everyone make fun with me!)
2014-11-11 18:11:36 Anubhav Balodhi
the easiest question ever...
2013-12-18 01:21:53 Samil Vargas
Man this is the easiest problem in the history but understand this is for freak people i could say that im one of those cause this problem is so easy just got to use long long int if you have time limit you are doing wrong
2012-05-07 15:01:13 Bahrul Halimi
i got WA.. :(
i've use 64-bit integer..
2012-05-07 14:57:49 arc
此题看不懂
2012-05-03 16:01:54 :D
Barely a tutorial problem. On top of that the wording seems to suggest you are looking for a number that can be expressed as product of exactly two primes, witch is not the case. You only need to remember to use 64-bit integers.
2012-04-06 16:00:30 manish sharma
the answer should be B only .... i don't know y it's giving me wrong answer
2012-03-16 14:01:42 magicsquare
Definitely tutorial :D
2012-03-15 13:21:42 shivamrana
Aviral ans is b only... ;)
check if u're not giving a new line after each test case...
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.