Một số nguyên dương có thể có nhiều ước nguyên tố phân biệt. Ví dụ: \(60 = 2^2 \times 3 \times 5\) có 3 ước nguyên tố phân biệt là 2, 3, 5.

Cho đoạn [L, R] và số K, hãy đếm số lượng số nguyên trong đoạn [L, R] có đúng K ước nguyên tố phân biệt.

Sử dụng sàng số học biến thể: tiền xử lý số ước nguyên tố phân biệt cho tất cả số đến R bằng cách cập nhật khi duyệt bội số.

Đầu vào

Một dòng duy nhất chứa ba số nguyên L, R, K (\(1 \le L \le R \le 10^6, 1 \le K \le 10\)).

Đầu ra

Số lượng số trong [L, R] có đúng K ước nguyên tố phân biệt.

Ví dụ

Input:
10 30 2

Output:
6

Giải thích

Các số có đúng 2 ước nguyên tố phân biệt: 10 \((2, 5)\), 14 \((2, 7)\), 15 \((3, 5)\), 21 \((3, 7)\), 22 \((2, 11)\), 26 \((2, 13)\).

Ràng buộc & Subtasks