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

Ba số nguyên dương ~A, B~ và ~K~ (~1 ≤ A ≤ B < 2^{31}~ 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~

Sample Test

Input 1

1 20 2

Output 1

5

Input 2

1 1000 4

Output 2

64