1113 - ProjectEuler 7
Description

前6个质数是2, 3, 5, 7, 11, 13。第6个质数是13。
输入n，输出第n个质数。

Input

第一行输入组数T， 接下来T行，每行一个整数n。 


Output

对于每组数据，输出一个数，表示第n个质数。


Examples

Input

3
3
6
10001

Output

5
13
104743
Hint

50%的数据：1 <= T <= 10，1 <= N <= 1001

100%的数据：1 <= T <= 100，1 <= N <= 100001

题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 55
通过次数 11
Stats
上一题
下一题