An là một nhà toán học nhỏ tuổi. Trong giờ học, thầy giáo giao cho An bài toán: đếm các số nguyên nằm trong đoạn \([L, R]\) mà tổng các chữ số của chúng chia hết cho một số nguyên dương K cho trước. An thử đếm thủ công với những số nhỏ thì được, nhưng thầy bảo R có thể lên tới \(10^{18}\) - quá lớn để ngồi đếm tay. An đành nhờ bạn tính hộ bằng một cách thông minh hơn.

Hãy giúp An giải bài toán này.

Định dạng đầu vào

• Một dòng chứa ba số nguyên \(L\), R và K (\(1 \le L \le R \le 10^{18}, 1 \le K \le 50\)).

Định dạng đầu ra

• In ra số lượng số nguyên trong đoạn \([L, R]\) có tổng các chữ số chia hết cho \(K\).

Ví dụ

Input:

10 30 3

Output:

7

Ràng buộc

• 20% số điểm ứng với \(R \le 10^6\)
• 30% số điểm ứng với \(R \le 10^{12}\)
• 50% số điểm còn lại không có ràng buộc gì thêm.