题目描述

前 6 个质数是 $2,3,5,7,11,13$，第 6 个质数是 13。现在需要回答 $n$ 次询问，每次给出正整数 $q$，请输出第 $q$ 个质数。

输入格式

第一行一个整数 $n$。接下来 $n$ 行，每行一个正整数 $q$。

输出格式

输出 $n$ 行。对于每次询问，输出第 $q$ 个质数。

样例

3
6
1
2

13
2
3

数据范围

$n\le 10000$，$1\le q\le 1000$，答案不超过 $10^7$；第 1000 个质数是 7919。