Với một số nguyên \(P(P \geq 2)\), ta có thể phân tích \(P\) thành tích của các thừa số nguyên tố, trong đó có một thừa số nguyên tố nhỏ nhất.

Ví dụ: \(100 = 2 \times 2 \times 5 \times 5\) thì số 2 là thừa số nguyên tố nhỏ nhất của 100; \(15 = 3 \times 5\) thì số 3 là thừa số nguyên tố nhỏ nhất của 15; \(17 = 17\) thì 17 là thừa số nguyên tố nhỏ nhất của 17.

Cho trước một dãy gồm \(n\) số nguyên tố \(a_{1},a_{2},\ldots,a_{n}\) và một số nguyên dương \(k\).

Yêu cầu: Đếm xem trong đoạn \(\lbrack 2;k\rbrack\) có bao nhiêu số nguyên có thừa số nguyên tổ nhỏ nhất là \(a_{i}\ (1 \leq i \leq n)\).

Dữ liệu vào:

+ Dòng đầu tiên hai số nguyên \(n\) và \(k\) (\(1 \leq n \leq 10^{5};2 \leq k \leq 10\hat{}6)\).

+ Dòng thứ hai ghi \(n\) số nguyên tố \(a_{1},a_{2},\ldots,a_{n}\) trên cùng một dòng và giữa các số cách nhau bởi một dấu cách \((2 \leq a_{i} \leq k,\ 1 \leq i \leq n)\).

Kết quả:

+ Gồm \(n\) dòng, với dòng thứ \(i\) là số lượng số nguyên trong đoạn \(\lbrack 2,k\rbrack\) có thừa số nguyên tố nhỏ nhất là \(a_{i}\).

Ví dụ:

Ràng buộc:

+ Có 50% số test tương ứng với 50% số điểm có \(n \leq 10^{3},k \leq 10^{3}\)

+ Có 50% số test còn lại tương ứng với 50% số điểm không có ràng buộc nào thêm.