Ước nguyên tố

Số tự nhiên $m$ được gọi là ước nguyên tố của số nguyên dương $n$ nếu $n$ chia hết cho $m$ và $m$ là số nguyên tố.

Ví dụ: Số 12 có 2 ước nguyên tố là 2 và 3; số 30 có 3 ước nguyên tố là 2, 3 và 5.

Yêu cầu: Cho $Q$ truy vấn, mỗi truy vấn gồm ba số nguyên $a, b, k$.
Với mỗi truy vấn, hãy xác định số lượng các số nguyên $x$ thỏa mãn: $a \le x \le b$ và có số lượng ước nguyên tố không nhỏ hơn $k$.

Vào từ tệp văn bản BAI2.INP có cấu trúc:

• Dòng thứ nhất chứa số nguyên dương $Q$ là số lượng truy vấn ($1 \le Q \le 10^5$).
• $Q$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $a, b, k$ ($1 \le a \le b \le 10^6$; $0 \le k \le 7$).

Ghi ra tệp văn bản BAI2.OUT gồm $Q$ dòng, mỗi dòng ghi một số nguyên duy nhất là kết quả tương ứng với mỗi truy vấn.

• Có 60% số test ứng với 60% số điểm của bài thỏa mãn: $Q = 1$; $1 \le a \le b \le 10^3$.
• Có 20% số test khác ứng với 20% số điểm của bài thỏa mãn: $Q = 1$; $10^3 < a \le b \le 10^6$.
• 20% số test còn lại ứng với 20% số điểm của bài không có ràng buộc gì thêm.