Bài 2 : Ước nguyên tố (6.0 điểm)

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ố.

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\).

Input

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)\).

Output

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.

Example

1
25 30 2

3

Scoring

• 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.