Project Euler #123: Prime square remainders

_{This problem is a programming version of Problem 123 from projecteuler.net}

Let be the th prime: , and let be the remainder when is divided by .

For example, when , and .

The least value of for which the remainder first exceeds is .

Find the least value of for which the remainder first exceeds .

Input Format

The first line of input contains , the number of test cases.

Each test case consists of a single line containing a single integer, .

Constraints

Output Format

For each test case, output a single line containing a single integer, the requested answer.

Sample Input

1
100

Sample Output

Explanation

As noted above, the first for which the remainder exceeds is . The remainder when is , which definitely exceeds . You may easily check that the remainder doesn't exceed when .