B. Максимальная прочность
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Федя играет в новую игру «The Legend of Link», в которой одной из способностей персонажа является монтаж двух материалов в одно оружие. Каждый материал имеет свою прочность, которую можно обозначить целым положительным числом $$$x$$$. Прочность полученного оружия определяется как сумма модулей разностей цифр в десятичной записи чисел на каждой позиции.

Формально, пусть первый материал имеет прочность $$$X = \overline{x_{1}x_{2} \ldots x_{n}}$$$, а второй имеет прочность $$$Y = \overline{y_{1}y_{2} \ldots y_{n}}$$$. Тогда прочность оружия вычисляется как $$$|x_{1} - y_{1}| + |x_{2} - y_{2}| + \ldots + |x_{n} - y_{n}|$$$. Если числа имеют различные длины, то более короткое число дополняется ведущими нулями.

Федя имеет в своем инвентаре в неограниченном количестве материалы со всеми возможными прочностями от $$$L$$$ до $$$R$$$ включительно. Помогите ему найти максимально возможную прочность оружия, которую он может получить.

Число $$$C = \overline{c_{1}c_{2} \ldots c_{k}}$$$ определяется как число, полученное последовательной записью цифр $$$c_1, c_2, \ldots, c_k$$$ слева направо, т.е. $$$10^{k-1} \cdot c_1 + 10^{k-2} \cdot c_2 + \ldots + c_k$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая и единственная строка каждого набора входных данных содержит два целых числа $$$L$$$ и $$$R$$$ ($$$1 \le L \le R < 10^{100}$$$) — десятичная запись чисел, обозначающих минимальную и максимальную прочность материалов, которые есть у Феди. Гарантируется, что числа $$$L$$$ и $$$R$$$ не содержат ведущих нулей.

Обратите внимание, что входные данные могут не помещаться в стандартные $$$32$$$-битные или $$$64$$$-битные целочисленные типы данных.

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимально возможную прочность оружия, которую может получить Федя из данных материалов.

Пример
Входные данные
6
53 57
179 239
13 37
132228 132228
54943329752812629795 55157581939688863366
88 1914
Выходные данные
4
19
11
0
163
28
Примечание

В первом наборе входных данных оружие, сделанное из материалов с прочностями $$$53$$$ и $$$57$$$, будет иметь максимально возможную прочность: $$$|5 - 5| + |3 - 7| = 4$$$.

Во втором наборе входных данных максимальная прочность достигается при материалах с прочностями $$$190$$$ и $$$209$$$: $$$|1 - 2| + |9 - 0| + |0 - 9| = 19$$$.

В четвёртом наборе входных данных есть только одна допустимая прочность, поэтому ответ $$$0$$$.

В шестом наборе входных данных максимальная прочность достигается при материалах с прочностями $$$1909$$$ и $$$90$$$: $$$|1 - 0| + |9 - 0| + |0 - 9| + |9 - 0| = 28$$$. Обратите внимание, что более короткое число было дополнено ведущими нулями.