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 chữ số chia hết cho ~k~.

Input

Dữ liệu vào từ tệp CAU2.INP:

• Gồm 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~).

Output

Kết quả ghi ra tệp CAU2.OUT:

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

Ví dụ

Ví dụ 1

Input

1 10 2

Output

1

Giải thích: 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

Input

19 88 8

Output

3

Giải thích: Các số thỏa mãn điều kiện là: ~53, 71, 79~.

Giới hạn

• ~1 \le L \le R \le 10^7~; ~1 \le k \le 100~.
• Subtask 1: 35% điểm, ~1 \le L, R \le 10~;
• Subtask 2: 20% điểm, ~1 \le L \le R \le 100~;
• Subtask 3: 45% điểm còn lại không có thêm ràng buộc bổ sung.