Given an integer N you have to find smallest prime number which comes after N, means smallest prime which is greater than N.

Input

First line contains T (1 <= T <= 1000) the number of test cases. Each of next T lines contain one integer N. 1 <= N <= 10^9.

Output

For each test case print the answer in a new line.

Example

Input:
2
5
21

Output:
7
23