Палиндромные диапазоны 2
(Время: 0,5 сек. Память: 32 Мб Сложность: 94%)
Натуральное число является палиндромом, если его десятичное представление (без ведущих нулей) является палиндромной строкой (строкой, которая читается одинаково слева направо и справа налево). Например, числа 7, 55, 979 являются палиндромами.
Диапазон натуральных чисел называется палиндромным, если он содержит четное количество палиндромов. Диапазон [A, B], где A ≤ B, определяется как последовательность натуральных чисел от A до B (включительно).
Диапазон [A1, B1] является поддиапазоном [A, B], если A ≤ A1 ≤ B1 ≤ B. Ваша задача – определить: сколько существует палиндромных поддиапазонов [A, B] по модулю 109 + 7.
Входные данные
Входной файл INPUT.TXT содержит натуральное число T – количество тестов. В следующих T строках содержится по два числа A и B, разделенные пробелом. (1 ≤ T ≤ 100, 1 ≤ A ≤ B ≤ 10200).
Выходные данные
В выходной файл OUTPUT.TXT выведите на каждый тест ответ на задачу с новой строки.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4
1 9
13 17
11 11
1 7 | 20
15
0
12 |
Автор задачи
Владимир Игоревич Лукьянчиков
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
