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
kaneki13: 2018-10-12 23:14:07

Can it be solved using miller rabin test?
or did anyone use segment sieves?

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


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