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
2012-03-15 09:00:02 theycallhimavi
certainly B except zero should be the answer but it is not.. :/
2012-03-13 07:25:59 Shashank_Jain
most ironic question ever!!!
2012-02-24 13:04:25 (^_^)
should not be in the classical.
its easy for tutorial too.
2012-02-10 17:26:22 DoRMaNT_LuNaTiC
it should not have 0.25 points weightage
2012-02-08 19:00:11 kartik
so any number can be expressed here as product of primes ...can anyone suggest cases where a number can't be ?
2012-02-06 09:59:44 Abhishek Goel
LOL Question
2012-01-27 12:27:36 Lukmanul Hakim
Is any number can be expressed as product of primes? :O
2012-01-26 21:06:03 Garima Sachan
Ye
2012-01-26 15:56:14 vicky raj
if a=1 and b=12.is 12 the output(2*2*3).
2012-01-26 15:55:02 vicky raj
is the number to be printed is product of two primes?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.