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.