AU12 - Prime After N

no tags 

Given an integer N you have to find smallest prime number which comes after N, means smalltest 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


hide comments
John and the cows: 2013-08-18 03:48:37

easy one :)

Mitch Schwartz: 2011-10-28 09:13:12

This is duplicate of another problem in Tutorial, NOVICE24, but with different test data.


Added by:amit karmakar
Date:2011-02-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64