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: BF GOSU

hide comments
2018-05-28 01:09:34
This really belongs in classical. Excellent problem.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.