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-01-24 01:46:49 accept
really it is helpful for Balaji!!!

Last edit: 2012-01-16 21:40:09
2012-01-24 01:46:49 Smit Mehta
TUTORIAL!!!
2012-01-24 01:46:49 germinating
move this to tutorial ........
L:(
2012-01-24 01:46:49 Mitch Schwartz
:\
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.