Розіграш Квитків
Промоутери концерту Bon Jovi Tour 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.
Вихідні дані
Для кожного концерту виведіть один рядок, що містить кількість квитків, обраних під час розіграшу квитків.