Với một số nguyên dương ~x \ge 2~, gọi ~f(x)~ là ước số nguyên tố lớn nhất của ~x~.

Cho hai số ~n,q~ và ~q~ câu hỏi. Mỗi câu hỏi cho một số nguyên dương ~k~, hãy cho biết trong phạm vi từ ~2~ tới ~n~ có bao nhiêu giá trị ~x~ thỏa mãn ~f(x) \le k~.

Input

Dòng đầu chứa hai số nguyên dương ~n,q~.

~q~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~k~.

Output

In ra ~q~ dòng, dòng thứ ~i~ là đáp số của câu hỏi thứ ~i~.

Subtask

• 60% số điểm: ~n \le 10^4~, ~q \le 10~.
• 40% số điểm: ~2 \le n \le 10^6~, ~q \le 10^6~, ~1<k \le 10^6~.</li>

Ví dụ

10 4
2
5
3
8

3
8
6
9