Ассасины 21 века более продвинуты, чем их предки. Так, наконец заполучив Яблоко Эдема, Каллум Линч спрятал его в хорошо охраняемом сейфе. Код к сейфу он поставил довольно длинный, чтобы никто не смог его взломать.
Однако, многочисленные попытки тамплиеров вскрыть сейф привели к следующему наблюдению: код от сейфа представляет собой «арифметическое число». Число называется арифметическим, если его цифры образуют арифметическую прогрессию по модулю 10: ,
, ... . Также тамплиерам известны границы на число, представляющее собой код — оно не меньше l и не больше r.
Исходя из всей этой информации, новая предводительца тамплиеров, София Райлин, просит вас помочь найти количество возможных кодов к сейфу, удовлетворяющих всем ограничениям. Помогите ей!
В первой строке содержится число l — левая граница на число, представляющее код от сейфа (1 ≤ l ≤ 10105).
Во второй строке содержится число r — правая граница (l ≤ r ≤ 10105).
В единственной строке выведите количество возможных кодов к сейфу, являющихся арифметическими числами и лежащими в отрезке [l, r].
Первая группа тестов состоит из тестов, для которых выполняется ограничение 1 ≤ l ≤ r ≤ 109, r - l ≤ 105. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 18 баллов.
Вторая группа тестов состоит из тестов, для которых выполняется ограничение 10k ≤ l ≤ r < 10k + 1 для некоторого целого k. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 23 балла.
Третья группа тестов состоит из тестов, для которых выполняется ограничение l = 1, r = 10k для некоторого целого k. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 21 балл.
Четвертая группа тестов состоит из тестов, для которых выполняется ограничение 1 ≤ l ≤ r ≤ 10105. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 38 баллов.
Обратите внимание на возможность узнать результат проверки вашего решения на всех тестах, нажав на ссылку «Request feedback» на вкладке «Runs».
9
15
7
90
110
11
В первом тестовом примере подходят все числа из данного отрезка.
Во втором тестовом примере подходят числа 90-99 и 109.