F. Интересные числа
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп считает число x является q-интересным, если в нем встречается не более q идущих подряд одинаковых цифр.

Даны три целых числа: l, r и k. Поликарп хочет найти количество k-интересных числе в промежутке от l до r включительно.

Входные данные

Три целых числа: l, r, k. 0 ≤ l < r ≤ 1018, 1 ≤ k ≤ 18. Числа разделены пробелом.

Выходные данные

Единственное целое число — количество чисел в промежутке с не более, чем k идущими подряд одинаковыми цифрами.

Примеры
Входные данные
0 1000000000000000000 1
Выходные данные
168856464709124011
Входные данные
0 100 2
Выходные данные
101
Входные данные
123 456 2
Выходные данные
331