Super Prime

Time limit1sMemory limit1024 MB

Summary

Given n, print the n-th super prime, where a super prime is a prime whose index among all primes is also prime. Up to 1000 queries with n up to 3000.

Level: Easy3 of 10
Topics: Number theory, Sorting
Solved: No attempts yet

Problem

Primes are a central concept for anyone who loves mathematics. A prime is a natural number greater than $1$ whose only divisors are $1$ and itself. Heujiro thought that some primes are even more special.

Call a prime $p$ a super prime if the following holds. Let $p$ be the $k$ -th smallest of all primes. Then $k$ is also prime.

Given an integer $n$ , write a program that prints the $n$ -th smallest super prime.

Input

The first line contains the number of test cases $T$ ( $1 \le T \le 1000$ ). Each of the next $T$ lines contains one integer $n$ ( $1 \le n \le 3000$ ).

Output

For each test case, print the $n$ -th smallest super prime on its own line.

Examples1

Example 1
Input
```
5
1
5
9
11
3000
```
Expected output
```
3
31
83
127
318137
```