PARPRIME - Partial Primes

Partial prime numbers are numbers which do not have any factors in a given range.

If x is a partial prime number, then the non-divisible range must be a non-empty contiguous subset of range [2, x-1].

Given the non-divisible range [a, b], find the smallest partial prime number for the given range.

Input

The first line consists of an integer t, the number of test cases. For each test case, you are given two integers a and b denoting the non-divisible range [a, b].

Output

For each test case, find the smallest partial prime number for the given range.

Constraints

1 <= t <= 10^3

2 <= b <= 10^7

2 <= a <= b

Example

Input:
3
2 5
5 7
8 23

Output:
7
8
25

Added by:cegprakash
Date:2016-10-22
Time limit:10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: MAWK BC BF NCSHARP COFFEE DART FORTH GOSU JULIA KTLN OCT PROLOG PYPY3 R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2016-11-26 22:58:36 cegprakash
For those who get TLE, try to think of the range where the answer lies.

Last edit: 2016-11-26 22:59:03
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.