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 ≤ x ≤ 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 ≤ Q ≤ 10⁵).
- Q dòng tiếp theo, mỗi dòng chứa ba số nguyên a, b, k (1 ≤ a ≤ b ≤ 10⁶; 0 ≤ k ≤ 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.

Scoring

- Có 60% số test ứng với 60% số điểm của bài thỏa mãn: Q = 1; 1 ≤ a ≤ b ≤ 10³.
- Có 20% số test khác ứng với 20% số điểm của bài thỏa mãn: Q = 1; 10³ < a ≤ b ≤ 10⁶.
- 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.

Example

input

1
25 30 2

output

3

Note

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