ABA12A - Help Balaji!

no tags 

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.


hide comments
theycallhimavi: 2012-03-15 09:00:02

certainly B except zero should be the answer but it is not.. :/

Shashank_Jain: 2012-03-13 07:25:59

most ironic question ever!!!

(^_^): 2012-02-24 13:04:25

should not be in the classical.
its easy for tutorial too.

DoRMaNT_LuNaTiC: 2012-02-10 17:26:22

it should not have 0.25 points weightage

kartik: 2012-02-08 19:00:11

so any number can be expressed here as product of primes ...can anyone suggest cases where a number can't be ?

Abhishek Goel: 2012-02-06 09:59:44

LOL Question

Lukmanul Hakim: 2012-01-27 12:27:36

Is any number can be expressed as product of primes? :O

Garima Sachan: 2012-01-26 21:06:03

Ye

vicky raj: 2012-01-26 15:56:14

if a=1 and b=12.is 12 the output(2*2*3).

vicky raj: 2012-01-26 15:55:02

is the number to be printed is product of two primes?


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