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