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

Dữ liệu vào

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

Dữ liệu ra

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

Ràng buộc

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

Ví dụ

Input

1
25 30 2

Output

3

Giải thích
Từ \(25\) đến \(30\) có \(3\) số có từ \(2\) ước nguyên tố trở lên đó là \(26, 28\) và \(30\). Cụ thể:

• \(26\) có \(2\) ước nguyên tố là \(2\) và \(13\).
• \(28\) có \(2\) ước nguyên tố là \(2\) và \(7\).
• \(30\) có \(3\) ước nguyên tố là \(2, 3\) và \(5\).