Mã số hợp lệ (Valid Number)

Phiên bản: Phước Hưng OJ Extended

Đề bài

Một số nguyên dương $x$ có biểu diễn thập phân gồm $m$ chữ số

trong đó $d_1\ne0$, được gọi là hợp lệ nếu đồng thời thỏa mãn hai điều kiện:

• Với mọi $1\le i<m$, hai chữ số liên tiếp khác nhau, tức là $d_i\ne d_{i+1}$.
• Tổng các chữ số chia hết cho $K$, tức là

Cho ba số nguyên $L$, $R$ và $K$. Hãy đếm số nguyên $x$ thuộc đoạn $[L,R]$ là số hợp lệ.

Input

Gồm một dòng chứa ba số nguyên $L$, $R$ và $K$.

Output

In ra một số nguyên duy nhất — số lượng số hợp lệ thuộc đoạn $[L,R]$.

Subtask

• Subtask 1 — 0,5 điểm: $1\le L\le R\le10^6$; $1\le K\le100$.
• Subtask 2 — 0,5 điểm: $1\le L\le R\le10^{18}$; $K=1$.
• Subtask 3 — 1,0 điểm: $1\le L\le R\le10^{18}$; $1\le K\le100$.

Ví dụ

Ví dụ 1

Input

1 30 3

Output

10

Giải thích

Các số hợp lệ trong đoạn $[1,30]$ là

Mỗi số đều có các chữ số liên tiếp khác nhau và tổng các chữ số chia hết cho $3$.

Có tất cả $10$ số như vậy.

Ví dụ 2

Input

10 99 5

Output

17

Giải thích

Trong đoạn $[10,99]$, một số có dạng hai chữ số $ab$ là hợp lệ khi:

• $a\ne b$;
• $a+b$ chia hết cho $5$.

Có đúng $17$ số thỏa mãn đồng thời hai điều kiện trên.