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 x 2.

hide comments
sharif ullah: 2016-10-26 18:44:51

সবাই মজা নেয় (Everyone make fun with me!)

Anubhav Balodhi : 2014-11-11 18:11:36

the easiest question ever...

Samil Vargas: 2013-12-18 01:21:53

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

Bahrul Halimi: 2012-05-07 15:01:13

i got WA.. :(
i've use 64-bit integer..

arc: 2012-05-07 14:57:49

此题看不懂

:D: 2012-05-03 16:01:54

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.

manish sharma: 2012-04-06 16:00:30

the answer should be B only .... i don't know y it's giving me wrong answer

magicsquare: 2012-03-16 14:01:42

Definitely tutorial :D

shivamrana: 2012-03-15 13:21:42

Aviral ans is b only... ;)
check if u're not giving a new line after each test case...

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

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


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