Một số nguyên chia hết cho \(3\) thì tổng các chữ số của nó cũng chia hết cho \(3\).

Ví dụ: \(3702 \vdots 3\) và \(3+7+0+2 = 12 \vdots 3\).

Tính chất này cũng đúng đối với số \(9\).

Trong bài toán này, chúng ta sẽ dùng tính chất đó cho các số nguyên khác.

Input

• Một dòng duy nhất chứa ba số nguyên dương \(A, B\) và \(K\).

Output

• Số lượng số nguyên trong phạm vi từ \(A\) đến \(B\) mà chia hết cho \(K\), đồng thời, tổng các chữ số của nó cũng chia hết cho \(K\).

Constraints

• \(1 \le A \le B < 2^{31}\)
• \(0 < K < 100\)

Example

1 20 2

5

1 1000 4

64

Nguồn: http://lightoj.com/volume_showproblem.php?problem=1068 / https://toph.co/p/m-beautiful-numbers