Interesting Numbers

Vasya is a young mathematician. His dad often tells him stories from his own childhood, especially about how he collected stamps like many of his peers did. Every stamp had its own story, and Dad remembered all of them down to the smallest details. The most fascinating were the stories about how the stamps from the 'Rare Cars' series were obtained. Vasya loved these stories and decided to try the hobby himself. Since Vasya loved math more than rare cars, he decided to collect stamps with various numbers.

Vasya was persistent and often reached his goals. In a short time he collected stamps with every number from $a$ to $b$. Each stamp has exactly one number written on it. He never kept two stamps with the same number, so all numbers on the stamps are different.

Vasya also remembers the story behind each stamp. The most interesting stories belong to stamps whose number has at least $k$ identical digits in a row in its decimal notation. He calls these stamps interesting. For example, if $k = 2$, the stamps with 22, 111, 100, and 556 are interesting, while the stamps with 2, 121, and 1212 are not.

You are given $a$, $b$, and $k$. Count the interesting stamps with numbers from $a$ to $b$.

The input file contains three integers $a$, $b$ ($1 \le a \le b \le 4 \cdot 10^{18}$) and $k$ ($1 \le k \le 20$).

Print one integer to the output file, the answer to the problem.

In the first test, the interesting stamps are 11, 22, 33, 44, 55, 66, 77, 88, 99, and 100.

In the second test, the interesting stamps are 111, 112, 113, 114, 115, 116, 117, 118, 119, 122, and 133.