Федя играет в новую игру «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$$$-битные целочисленные типы данных.
Для каждого набора входных данных выведите одно целое число — максимально возможную прочность оружия, которую может получить Федя из данных материалов.
653 57179 23913 37132228 13222854943329752812629795 5515758193968886336688 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$$$. Обратите внимание, что более короткое число было дополнено ведущими нулями.
| Codeforces Round 879 (Div. 2) |
|---|
| Закончено |
