Задача C. Интересные числа ≡

Условие

При подготовке пакета были использованы материалы сайта школьных олимпиад по информатике.

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

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

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

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

Решения, работающие при 1 ≤ a ≤ b ≤ 10⁶ будут оцениваться из 40 баллов.

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

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

Формат входного файла

Во входном файле заданы три целых числа a, b (1 ≤ a ≤ b ≤ 4 ⋅ 10¹⁸) и k (1 ≤ k ≤ 20).

Формат выходного файла

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

Примеры тестов

1 100 2

10

111 133 2

11