Một số nguyên dương có thể có nhiều ước nguyên tố phân biệt. Ví dụ: 60 = 2² × 3 × 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 ≤ L ≤ R ≤ 10^6, 1 ≤ K ≤ 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).