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

Input

1 20 2

Output

10

Explanation

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

Example 2

Input

0 25 3

Output

9

Example 3

Input

2040 2050 5

Output

2

Explanation

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