Smallest Prime Greater Than N

A common problem in programming contests is to find the smallest prime number greater than a given integer. In this problem, you are given T test cases; for each test case, you must compute the smallest prime number that is strictly greater than the input integer N. You may use efficient methods for checking primality to solve this problem.

Definition: A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Note: Use efficient algorithms to ensure that your solution runs within the time constraints for large inputs.

inputFormat

The first line of input contains an integer T (1 ≤ T ≤ 100), representing the number of test cases. Each of the following T lines contains a single integer N (0 ≤ N ≤ 10⁶), for which you must find the smallest prime number greater than N.

outputFormat

For each test case, output the smallest prime number greater than N on a separate line.

## sample

2
10
15

11
17

</p>