Số may mắn

Nhà toán học Minh tin rằng mỗi số nguyên đều mang một "năng lượng" đặc biệt. Anh định nghĩa một số nguyên dương là may mắn đối với số nguyên dương \(K\) nếu đồng thời thỏa mãn hai điều kiện sau:

• Số đó chia hết cho \(K\).
• Tổng các chữ số của số đó cũng chia hết cho \(K\).

Ta đã biết rằng nếu một số chia hết cho \(3\) thì tổng các chữ số của nó cũng chia hết cho \(3\). Tính chất tương tự cũng đúng với số \(9\). Tuy nhiên, đối với các giá trị khác của \(K\), điều này không còn luôn đúng.

Yêu cầu. Cho ba số nguyên dương \(A\), \(B\) và \(K\). Hãy đếm xem có bao nhiêu số may mắn nằm trong đoạn \([A,B]\).

\InputFile

Gồm một dòng chứa ba số nguyên dương \(A\), \(B\) và \(K\).

Các giá trị thỏa mãn

$
1 \le A \le B < 2^{31},
$

$
1 \le K < 100.
$

\OutputFile

In ra số lượng số nguyên trong đoạn \([A,B]\) thỏa mãn cả hai điều kiện trên.

\Examples

\beginexample
\exmp
1 20 2

5

\exmp
1 1000 4

64

\endexample

\Scoring

• (30%) \(B \le 10^5\).
• (30%) \(B \le 10^7\).
• (40%) Không có ràng buộc bổ sung.

\endproblem