Limits 1s, 512 MB

A positive integer number n is called a prime number, if it is only divisible by 1 and nn itself, where 1n1\ne n. There exists an infinitely many prime numbers! But as the number gets larger, the distribution of primes among them gets less frequent.

You want to investigate the distribution of prime numbers. As a part of this investigation, you want to find out the largest prime number in a given range.

Input

The first line contains an integer QQ (1Q1051 ≤ Q ≤ 10^5), the number of queries that will be given. The next QQ lines will contain two integers lil_i (1li1 ≤ l_i) and rir_i (ri10000r_i ≤ 10000).

Output

For each line of query, print a single line, containing the largest prime in the range lil_i and rir_i inclusive. If there is no prime numbers in a given range, print -1 instead. Please see the samples for the exact formatting.

Sample

InputOutput
5
25 28
1 1
2 3
8 12
14 20
-1
-1
3
11
19

Submit

Login to submit.

Contributors

Statistics

85% Solution Ratio
fsshakkhorEarliest, Dec '16
Kuddus.6068Fastest, 0.0s
syed_tahsinLightest, 3.7 MB
Kuddus.6068Shortest, 217B
Toph uses cookies. By continuing you agree to our Cookie Policy.