Description

给出一个数 $N$，然后再给出 $N$ 个正整数，第 $i$ 个正整数表示为 $A_i$,要你输出从 $2$ 开始的第 $A_i$个素数的值(只输第 $A_i$ 个)，$A_i \le 5 \times 10^6$,$N$ 小于等于 $100$.

Format

Input

第一行一个整数 $N$;
接下来 $N$ 行每行一个整数 $i$。

Output

共 $N$ 行，每行一个 $A_i$ 表示结果。

Samples

3
2
10
15

3
29
47