Số nguyên tố thứ N

Dãy số nguyên tố theo thứ tự tăng dần bắt đầu bằng \(2, 3, 5, 7, 11, 13, \dots\) Với mỗi câu hỏi, cho số nguyên \(N\), hãy cho biết số nguyên tố đứng thứ \(N\) trong dãy (số nguyên tố thứ \(1\) là \(2\)).

Input

• Dòng đầu: số nguyên \(T\) là số câu hỏi.
• \(T\) dòng sau, mỗi dòng chứa một số nguyên \(N\).

Output

• \(T\) dòng, mỗi dòng là đáp án cho câu hỏi tương ứng.

Constraints

• \(1 \le T \le 10^3\)
• \(1 \le N \le 10^5\)

Sample Input

4
5
1
10
4

Sample Output

11
2
29
7