Bài 33.2. Mật Mã LPI và Bộ Giải Mã - [Độ khó: Khá]

Mô tả: Trong một trò chơi nhập vai phiêu lưu, có một hệ thống "Mật Mã LPI" bí ẩn. Giá trị LPI (Lowest Prime Index) của một số nguyên dương N được định nghĩa là chỉ số của ước số nguyên tố nhỏ nhất của N trong danh sách các số nguyên tố được sắp xếp tăng dần (ví dụ: chỉ số của 2 là 1, của 3 là 2, của 5 là 3, v.v.). Nếu N là 1, LPI của nó là 0. Bạn cần xây dựng một bộ giải mã có khả năng nhanh chóng tìm ra LPI của nhiều số.

INPUT FORMAT

Dòng đầu tiên chứa số nguyên MaxN (\(1 \le MaxN \le 10^7\)), là giới hạn trên của các số có thể xuất hiện trong truy vấn. Dòng thứ hai chứa số nguyên Q (\(1 \le Q \le 10^5\)), là số lượng truy vấn. Q dòng tiếp theo, mỗi dòng chứa một số nguyên X (\(1 \le X \le MaxN\)), là số cần tìm LPI.

OUTPUT FORMAT

Với mỗi truy vấn, in ra một số nguyên duy nhất trên một dòng, là giá trị LPI của X.

Ví dụ:

Input:

20
5
1
2
6
10
13

Output:

0
1
1
1
6

Giải thích:

• Danh sách các số nguyên tố và chỉ số của chúng: 2 (chỉ số 1), 3 (chỉ số 2), 5 (chỉ số 3), 7 (chỉ số 4), 11 (chỉ số 5), 13 (chỉ số 6), 17 (chỉ số 7), ...
• X = 1: Theo định nghĩa, LPI của 1 là 0.
• X = 2: Ước số nguyên tố nhỏ nhất là 2. Chỉ số của 2 là 1. LPI(2) = 1.
• X = 6: Các ước số nguyên tố của 6 là 2, 3. Ước số nguyên tố nhỏ nhất là 2. Chỉ số của 2 là 1. LPI(6) = 1.
• X = 10: Các ước số nguyên tố của 10 là 2, 5. Ước số nguyên tố nhỏ nhất là 2. Chỉ số của 2 là 1. LPI(10) = 1.
• X = 13: Ước số nguyên tố nhỏ nhất (và duy nhất) là 13. Chỉ số của 13 là 6. LPI(13) = 6.