Счастливые номера маршруток
Пассажиры бишкекских маршруток считают номер билета счастливым, если он делится на сумму своих цифр. Например, 132 счастливый (1 + 3 + 2 = 6, 132 = 6 · 22), а 133 — нет.
Для каждого из T вопросов l r найдите количество счастливых чисел среди l, l + 1, …, r.
Входные данные
В первой строке — число T (1 ≤ T ≤ 10). В каждой из следующих T строк — два целых числа l r (1 ≤ l ≤ r ≤ 10¹⁸).
Выходные данные
Для каждого вопроса выведите количество счастливых чисел на отрезке.
Пример 1
Вход:
3
1 20
100 200
1 100000
Выход:
13
27
11872
Пояснение
Однозначные числа счастливы все, из чисел 10…20 счастливы 10, 12, 18, 20. Всего на отрезке от 1 до 20 их 13.
Система оценивания
Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 15 % тестов r ≤ 10⁶, ещё в 5 % тестов r ≤ 10⁹.
Подсказка
Переберите сумму цифр S (от 1 до 162) и для каждой посчитайте числа с суммой цифр S, делящиеся на S, — динамикой по цифрам.
Комментарии