Digit Sum

Given three integers $L$, $R$, and $M$, count how many integers $x$ satisfy $L \le x \le R$ and have digit sum divisible by $M$.

The digit sum of a number is the sum of its decimal digits. For example, the digit sum of $2047$ is $2 + 0 + 4 + 7 = 13$.

Input

The input consists of a single line containing three integers $L$, $R$, and $M$.

Output

Print the number of valid integers in the range.

Constraints

• $0 \le L \le R < 10^{1000}$
• $1 \le M \le 200$
• $L$ and $R$ do not contain leading zeroes, unless the number is exactly 0

Example 1

1 20 2

10

Explanation

The valid values are $2$, $4$, $6$, $8$, $11$, $13$, $15$, $17$, $19$, and $20$.

Example 2

0 25 3

9

Example 3

2040 2050 5

2

Explanation

Only $2044$ and $2049$ have digit sum divisible by $5$.