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 ⋮3 và3+7+0+2 = 12 ⋮ 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: Ba số nguyên dương A, B và K (1 ≤ A ≤ B < 2³¹và 0 < K < 10000).

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.

Ví dụ:

Inp1:

1 20 2

Out1:

5

Inp2:

1 1000 4

Out2:

64