- All Contests
- ProjectEuler+
- Project Euler #123: Prime square remainders

# Project Euler #123: Prime square remainders

# 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**

```
5
```

**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 .