Next Prime

Given a positive integer n, find the next prime number after it.

Input

The first line has an integer t: the number of tests. After that, each line has a positive integer n.

Output

For each test, print the next prime after n.

Constraints

$1 \le t \le 20$

$1 \le n \le 10$^{12}$

Example

Input

5
1
2
3
42
1337

Output

2
3
5
43
1361