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\).

Dữ liệu:

• Gồm một dòng chứa ba số nguyên dương \(L\), \(R\), \(k\) \((1 \le L \le R \le 10⁷; 1 \le k \le 100)\).

Kết quả:

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

Input 1

1 10 2

Output 1

1

Note 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.

Input 2

19 88 8

Output 2

3

Note 2

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

Ràng buộc:

• \(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.