Farmer John has recently become quite bored working on the farm. Since he has nothing better to do, he starts writing down the integers 1, 2, 3, ... . Eventually, Farmer John realizes that he will never finish, so instead he starts looking at some of the properties of the numbers. He often likes to take a number and find its digit sum as follows:
Step 1: Add all of the digits of the current number together to form a new number.
Step 2: If the new number has exactly one digit, then that is the digit sum of the number. Otherwise, go back to step 1.
For example, the digit sum of 12345 is evaluated as follows:
1) 1 + 2 + 3 + 4 + 5 = 15.
2) 15 has two digits, so we continue:
1) 1 + 5 = 6.
2) 6 has only one digit, so the digit sum of 12345 is 6.
Write a program that, when given two numbers A and B (1 <= A <= B <= 10,000,000; B - A <= 1,000,000), and a single-digit number D, finds how many numbers between A and B, inclusive, have a digit sum of D.

Line 1: Three space-separated integers, respectively: A, B, and D

Line 1: A single integer representing the number of integers in between A and B that have a digit sum of D.

1 20 2

3