Đếm số nguyên tố

Cho ba số nguyên dương \(L, R, k\). Hãy đếm số lượng các số nguyên tố trong đoạn \([L; R]\) mà có tổng các chữ số chia hết cho \(k\).

Input

Một dòng chứa ba số nguyên dương \(L, R, k\) (\(1 \le L \le R \le 10^7\), \(1 \le k \le 100\)).

Ràng buộc:

• Subtask 1: \(35\%\) số điểm, \(1 \le L, R \le 10\);

• Subtask 2: \(20\%\) số điểm, \(1 \le L \le R \le 100\);

• Subtask 3: \(45\%\) số điểm còn lại không có thêm ràng buộc bổ sung.

Output

Ghi ra một số nguyên là kết quả tìm được.

Example 1

Input:

1 10 2

Output:

1

Example 2

Input:

19 88 8

Output:

3

Note

Ví dụ 1: trong đoạn \([1; 10]\) có các số nguyên tố là \(2, 3, 5, 7\). Trong đó chỉ có số \(2\) có tổng chữ số chia hết cho \(2\).

Ví dụ 2: các số thỏa mãn điều kiện là \(53, 71, 79\).