Задача №111902. Палиндромные числа
Вася очень любит изучать разные интересные классы чисел. Сегодня он изучает палиндромные числа.
Вася называет число палиндромным, если оно записывается одинаково слева направо и справа налево. При этом, Вася разрешает приписывать к числу несколько (возможно ни одного) лидирующих нулей. Например, числа 22, 4554, 12321, 5050 являются палиндромными. В частности, к числу 5050 необходимо приписать один ноль, чтобы получить 05050, которое читается одинаково слева направо и справа налево.
В числе прочих, Васю интересуют палиндромные числа, отличающиеся на 2. Для их исследования Вася рассматривает такие \(x\), что \(x-1\) и \(x+1\) являются палиндромными. Такие числа Вася называет междупалиндромными. Вася хочет найти количество междупалиндромных чисел \(x\) от \(L_k\) до \(R_k\) включительно для нескольких отрезков \([L_k, R_k]\).
Помогите Васе в этом нелегком деле!
Входной файл содержит несколько отрезков, которые интересуют Васю. В первой строке задано одно число \(T\) (\(1 \le T \le 2\,000\)) - количество отрезков. В каждой из следующих \(T\) строк заданы два числа \(L_{k}\) и \(R_{k}\) (\(1 \le L_{k} \le R_{k} \le 10^{18}\)) - границы отрезка.
Выведите \(T\) строк. В \(k\)-ой строке выведите одно число - количество междупалиндромных чисел в отрезке от \(L_{k}\) до \(R_{k}\) включительно.
От 17 до 24 палинромными являются числа 20 и 22. Поэтому единственное междупалиндромное число на отрезке \([18, 23]\) - это 21. Во втором примере, число 21 опять подходит. От 49 до 56 палинромными являются числа 50, 55. Междупалиндромных чисел на отрезке \([50, 55]\) нет.
3 18 23 21 21 50 55
1 1 0