| Автор: | И. Малиновский, П. Кунявский (Жюри XXI командной олимпиады школьников СПб по информатике) | Ограничение времени: | 2 сек | |
| Входной файл: | pnumbers.in | Ограничение памяти: | 256 Мб | |
| Выходной файл: | pnumbers.out |
Вася очень любит изучать разные интересные классы чисел. Сегодня он изучает палиндромные числа.
Вася называет число палиндромным, если оно записывается одинаково слева направо и справа налево. При этом, Вася разрешает приписывать к числу несколько (возможно ни одного) лидирующих нулей. Например, числа 22, 4554, 12321, 5050 являются палиндромными. В частности, к числу 5050 необходимо приписать один ноль, чтобы получить 05050, которое читается одинаково слева направо и справа налево.
В числе прочих, Васю интересуют палиндромные числа, отличающиеся на 2. Для их исследования Вася рассматривает такие x, что x − 1 и x + 1 являются палиндромными. Такие числа Вася называет междупалиндромными. Вася хочет найти количество междупалиндромных чисел x от Lk до Rk включительно для нескольких отрезков [Lk, Rk].
Помогите Васе в этом нелегком деле!
Входной файл содержит несколько отрезков, которые интересуют Васю. В первой строке задано одно число T (1 ≤ T ≤ 2 000) — количество отрезков. В каждой из следующих T строк заданы два числа Lk и Rk (1 ≤ Lk ≤ Rk ≤ 1018) — границы отрезка.
Выведите T строк. В k-ой строке выведите одно число — количество междупалиндромных чисел в отрезке от Lk до Rk включительно.
| № | Входной файл (pnumbers.in) |
Выходной файл (pnumbers.out) |
|---|---|---|
| 1 | |
|