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~

Yêu cầu: Cho số ~n~ và ~q~ câu hỏi, mỗi câu hỏi cho bởi số nguyên dương ~k~. Bạn hãy cho biết trong phạm vi từ ~2~ tới ~n~ có bao nhiêu giá trị ~x~ mà ~f(x) \le k~. Dữ liệu: Vào từ thiết bị nhập chuẩn

• Dòng 1 chứa hai số nguyên dương ~n, q~ cách nhau bởi dấu cách (~2 \le n \le 10^6, q \le 10^6~)
• ~q~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~k~ ứng với một câu hỏi (~2 \le k \le n~)

Kết quả: Ghi ra thiết bị xuất chuẩn ~q~ dòng, ứng với mỗi câu hỏi, ghi ra một số nguyên trên một dòng là đáp số của câu hỏi tương ứng

Sample Input

10 4
2
5
3
8

Sample Output

3
8
6
9

Giải thích

Từ 2 tới 10 có:

3 số ~x~ có ~f(x) \le 2: 2, 4, 8~

8 số ~x~ có ~f(x) \le 5: 2, 3, 4, 5, 6, 8, 9, 10~

6 số ~x~ có ~f(x) \le 3: 2, 3, 4, 6, 8, 9~

9 số ~x~ có ~f(x) \le 8: 2, 3, 4, 5, 6, 7, 8, 9, 10~

Bộ test chia làm 2 subtask:

60% số điểm ứng với các test có ~n \le 10^4; q \le 10~

40% số điểm ứng với test không có ràng buộc bổ sung