Generate a prime number greater than a given number

Given a number N, generate the least prime number greater than N.
N is an integer with 1-10 digits.
Do not use the basic brute force primality testing algorithm.

Input format:

The first line represents the number of test cases T.
The next T lines are numbers with 1-10 digits

Sample Input file:

5
10
100
1000
10000
100000

Output format:

There will be T lines that have the T numbers just greater than thenumber given.

Sample Output file:

11
101
1009
10007
100003