Розыгрыш билетов
Промоутеры концертов тура Bon Jovi 2013 решили продавать билеты на концерты через лотереи. Правила довольно просты. Для каждого концерта фанаты могут подать заявку на билеты онлайн и получить уникальные номера бронирования. Важно, чтобы для каждого концерта номера, распределяемые онлайн, были последовательными неотрицательными целыми числами, начиная с 0. К сожалению, когда организаторы попытались случайным образом выбрать номера бронирования, они обнаружили, что используемый ими генератор псевдослучайных чисел работает крайне медленно. Чтобы минимизировать количество обращений к генератору, они придумали своеобразный, но вполне справедливый способ распределения билетов.
Как только бронирование на концерт завершается, организаторы определяют количество заявок M и выбирают одно случайное целое число Z из множества {0, ..., M - 1} (помните, фанаты получают числа от 0 до M - 1). Целое число Z — это единственный объект, который организаторы должны выбрать случайным образом! Наконец, чтобы завершить правила отбора, организаторы определяют целое число r > 0, которое оказывает прямое влияние на количество выбранных билетов.
Теперь, используя Z и r, билеты выбираются детерминированно следующим образом. Для номеров бронирования 0, ..., M - 1 и числа Z рассматриваются их десятичные представления длиной n, где n — это длина представления M - 1 без ведущих нулей. Таким образом, десятичные представления оставшихся чисел дополняются слева ведущими нулями, если это необходимо. Если z[1] ... z[n] обозначает такое представление для Z, то владелец номера a[1] ... a[n] получает билет, если и только если строки z[1] ... z[n] и a[1] ... a[n] имеют общую непрерывную подстроку длиной r или более, которая начинается на той же позиции. Формально говоря, он или она получает билет, если существует индекс i, такой что 1 ≤ i ≤ n - r + 1, для которого z[i] ... z[i+r-1] = a[i] ... a[i+r-1]. Например, если Z = 56743 и r = 3, то фанат с номером бронирования 06740 получает билет, но фанат с номером 56143 не получает.
Ваша задача — помочь организаторам оценить, для заданных чисел M, Z и r, точное количество билетов, выбранных таким образом.
Входные данные
Первая строка содержит количество концертов C (1 ≤ C ≤ 5000). Далее следуют C строк, каждая из которых содержит три целых числа M, Z и r (0 < M ≤ 10^18, 0 ≤ Z ≤ M - 1 и r ≥ 1). Вы можете безопасно предположить, что r меньше или равно длине десятичного представления M - 1.
Выходные данные
Для каждого концерта выведите одну строку, содержащую количество билетов, выбранных во время розыгрыша билетов.