E. Erasmus Valthron
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Erasmus Valthorn is the Chief Archivist of the Celestial Library of Numeris — a vast hall where every integer from 1 to N exists as a physical tome, its spine engraved with the number it represents.

After decades of cataloguing by mere numeric order, Erasmus has grown restless. He believes that numbers have a true identity — not their face value, but their prime essence: the sorted sequence of prime factors that compose them.

He calls this the Canonical Form of a number. For example:

$$$48 = 2 \times 2 \times 2 \times 2 \times 3 \quad \Rightarrow \quad [ 2, 2, 2, 2, 3 ] $$$

$$$9 = 3 \times 3 \quad \Rightarrow \quad [ 3, 3 ] $$$

Erasmus now wishes to rearrange all tomes according to their Canonical Form, sorted lexicographically. Under this order, the tome of 48 precedes the tome of 9, since the first element of its sequence — 2 — is less than 3.

The number 1, having no prime factors, is represented by the empty sequence [ ], which is lexicographically smallest of all, and thus occupies the very first shelf.

However, Erasmus is old and forgetful. He keeps losing track of where specific tomes end up in the new arrangement. He has written down Q questions — each asking: "In this new order, which number sits at position K?"

Help Erasmus answer his queries before the next lunar eclipse!

Input

The first line contains two integers $$$N$$$ and $$$Q$$$ $$$(1 \leq N \leq 10^6,\ 1 \leq Q \leq 10^5)$$$, the number of tomes in the library and the number of queries Erasmus has written down.

Each of the next $$$Q$$$ lines contains a single integer $$$K_i$$$ $$$(1 \leq K_i \leq N)$$$, a position in the sorted arrangement.

Output

For each query, print a single integer — the number occupying position $$$K_i$$$ in Erasmus's new ordering.

Examples
Input
10 10
1
2
3
4
5
6
7
8
9
10
Output
1
2
4
8
6
10
3
9
5
7
Input
10 4
1
4
7
10
Output
1
8
3
7
Input
5 1
5
Output
5