Cho các số nguyên a, b và k. Nhiệm vụ của bạn là đếm trong đoạn [a, b] có bao nhiêu số có đúng k ước số nguyên tố (số nguyên tố là số chỉ có đúng hai ước là 1 và chính nó, ví dụ : 2, 3, 7, 11, ...).
Input: integer a, b, k
(2 ≤ a, b ≤ 107, 1 ≤ k ≤ 109)
Output: integer
Một số duy nhất là đáp án tìm được
Ví dụ
INPUT
OUTPUT
10 13 2
2
Với a = 10, b = 13, k = 2 thì kết quả là 2.
Trong các số {10, 11, 12, 13} thì 10 và 12 có hai ước số nguyên tố (với 10 là 2 và 5 còn 12 là 2 và 3).