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