After a long day at work, Santa comes home only to discover that his newborn reindeer have been numbered wrong by Mrs. Clause.

Normally, the ~N~ baby reindeer would be numbered ~1, 2, ..., N~. However, Mrs. Clause has absentmindedly numbered the ~i~th reindeer the value of the ~i~th prime number instead.

Santa is tired, so he wants you to deal with the logistic problems that arise with this new numbering. His assistant will ask you ~Q~ questions. The ~i~th question will ask you for the regular number of the reindeer with the current number ~a_i~. You must find the value of this regular number or that no reindeer is labeled the given number.

Input Specification

The first line will contain two space-separated integers, ~N~ and ~Q~ ~(1 \le N, Q \le 2 \cdot 10^5)~.

The next ~Q~ lines will each contain one integer, ~a_i~ ~(1 \le a_i \le 2 \cdot 10^6)~.

Output Specification

For each question, output the regular number of the reindeer in question on a separate line. If there is no reindeer with that number, output -1 instead.

Constraints

Subtask 1 [30%]

~1 \le N \le 10^4~

Subtask 2 [70%]

No further constraints.

Sample Input

5 4
2
5
11
20

Sample Output

1
3
5
-1

Explanation for Sample Output

~2~ is the first prime number, so its regular number is ~1~.

~5~ and ~11~ are the third and fifth prime numbers respectively, so their regular numbers are ~3~ and ~5~.

~20~ is not a prime number, so it has no regular number attached to it.