This Question is Simple and Straight Forward . You are given a number , you have to find the next prime number.

Input

First line contains an integer t denoting number of test cases
Next t lines contains an integer n

Output

Print t lines containing the next prime

Subtasks
1<=t<=10 , 1<=n<=100 ( 10 Points)
1<=t<=100 , 1<=n<=100000(15 points)
1<=t<=1000 , 1<=n<=10000000(20 points)
1<=t<=100000 , 1<=n<=10000000(25 points)
1<=t<=200000 , 1<=n<=10000000 (30 points)