Cho dãy số nguyên dương gồm ~n~ số. Với mỗi ~i(1..)~, hãy cho biết giá trị của số nguyên tố thứ ~ai~.

Input:

• Dòng 1: Ghi Số nguyên dương ~n (n \leq 10^5)~
• Dòng 2: Ghi ~n~ số nguyên dương ~ai (ai \leq 10^5)~ (các số trên ~1~ dòng được ghi cách nhau ~1~ dấu cách)

Output:

• Ghi kết quả trên ~n~ dòng tương ứng

Sample input

2
4 10

Sample output

7
29

Subtask

• ~50\%~ số test có ~n \le 10^3~