Given three integers L, R, and K, find the number of integers X such that L \le X \le R and the digital root of X is exactly equal to K.
The digital root of a positive integer is found by summing its digits repeatedly until a single-digit number is obtained.
Input
Three integers L, R, and K (1 \le L \le R \le 10^{18}, 1 \le K \le 9).
Output
Print a single integer representing the total number of integers in the range [L, R] that have a digital root equal to K.
Examples
| standard input | standard output |
|---|
| 10 20 2
| 2
|
| 1 100 9
| 11
|
Note
Digital root of number 456 is calculated as follows:
1. 4+5+6 = 15
2. 1+5 = 6
So digital root of 456 is 6.