29427번 - Интересные числа 다국어

Вася --- юный математик. Папа часто рассказывает ему истории связанные с папиным детством, особенно то, что он, как и многие его сверстники, любил коллекционировать марки. У каждой марки была своя история, и папа Васи все эти истории помнил до последних мелочей. Особенными были истории о том, как были добыты марки из серии <<Раритетные автомобили>>. Васе очень нравились рассказы его отца. Он тоже решил попробовать себя в этом деле. Так как Вася любил не раритетные автомобили, а математику, он решил собирать марки с различными числами.

Вася был очень упорным во всех своих начинаниях и часто добивался своей цели. Поэтому за небольшой отрезок времени он смог собрать марки со всеми числами от $a$ до $b$. При этом на каждой марке написано ровно одно число. Вы конечно же понимаете, что марок с одинаковыми числами он не оставлял в своей коллекции, поэтому на всех марках были записаны различные числа.

Вася так же хорошо, как и его папа, запомнил все истории, связанные с каждой маркой. Особенно интересные истории были связаны с марками, на которых было написано такое число, у которого в десятичной записи есть хотя бы $k$ одинаковых цифр подряд. Такие марки он назвал интересными. Например, если $k = 2$, то марки с числами 22, 111, 100, 556 являются интересными, а с числами 2, 121, 1212 не являются.

Вам заданы числа $a$, $b$ и $k$. Требуется посчитать количество интересных марок с числами от $a$ до $b$.

Во входном файле заданы три целых числа $a$, $b$ ($1 \le a \le b \le 4 \cdot 10^{18}$) и $k$ ($1 \le k \le 20$).

В выходной файл выведите единственное целое число --- ответ на задачу.

В первом примере интересными являются марки с числами $11$, $22$, $33$, $44$, $55$, $66$, $77$, $88$, $99$ и $100$.

Во втором примере интересными являются марки с числами $111$, $112$, $113$, $114$, $115$, $116$, $117$, $118$, $119$, $122$ и $133$.