C :: Next Prime

Time Limit: 10 Seconds    Memory Limit: 131072 KB

Given an integer n, with 0 <= n <= 4*10^9, your task is to find the smallest prime number which is not less than n.

Input

The first line of input will be a number specifying the number of lines that follow. Each of the following lines will be an integer n.

Output

For each of these lines, output the smallest prime not less than n, on a separate line.

Sample Input

3
6
20
100

Sample Output

7
23
101

Submit