C. Неудачливые номера
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В этой задаче, в отличие от задачи А, требуется искать наименее удачливый номер, а не наиболее удачливый.

Обратите внимание, что ограничения на эту задачу отличаются от ограничений на задачу А.

В городе Олимп-Сити недавно запустили производство персональных звездолетов. Теперь каждый житель Марса сможет купить себе такое средство передвижения и недорого летать на другие планеты.

Естественно, у каждого звездолета есть номер — некоторое целое положительное число $$$x$$$. Назовем удачливостью числа $$$x$$$ разность между наибольшей и наименьшей цифрами этого числа. Например, у числа $$$142857$$$ наибольшая цифра равна $$$8$$$, а наименьшая — $$$1$$$, поэтому его удачливость равна $$$8-1=7$$$. А у числа $$$111$$$ все цифры равны $$$1$$$, поэтому его удачливость равна нулю.

Лаксап — известный марсианский блогер, который часто летает в разные уголки Солнечной системы. Чтобы выпускать интересные видео еще быстрее, он решил купить себе звездолет. Придя в магазин, он увидел звездолеты с номерами с $$$l$$$ по $$$r$$$ включительно. Находясь в магазине, Лаксап заинтересовался, какие из звездолетов имеют наименее удачливые номера.

Поскольку звездолетов в магазине много, а Лаксап не умеет программировать, то Вы должны помочь блогеру и написать программу, которая отвечает на его вопрос.

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

В первой строке находится целое число $$$t$$$ ($$$1 \le t \le 600$$$) — количество наборов входных данных.

В каждой из следующих $$$t$$$ строк находится описание набора входных данных. Описание состоит из двух целых чисел $$$l$$$, $$$r$$$ ($$$1 \le l \le r \le 10^{18}$$$) — наибольший и наименьший номера звездолета в магазине.

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

Выведите $$$t$$$ строк, по одной строке на каждый набор входных данных, содержащую номер наименее удачливого звездолета в магазине.

Если способов выбрать наименее удачливый номер несколько, то выведите любой из них.

Пример
Входные данные
5
59 63
42 49
48 53
90 90
1 100
Выходные данные
63
44
53
90
1
Примечание

Рассмотрим первые два набора входных данных.

  • удачливость числа $$$59$$$ равна $$$9 - 5 = 4$$$;
  • удачливость числа $$$60$$$ равна $$$6 - 0 = 6$$$;
  • удачливость числа $$$61$$$ равна $$$6 - 1 = 5$$$;
  • удачливость числа $$$62$$$ равна $$$6 - 2 = 4$$$;
  • удачливость числа $$$63$$$ равна $$$6 - 3 = 3$$$.
Таким образом, наименее удачливый номер — $$$63$$$.

В пятом тестовом примере наименьшую удачливость имеют числа $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, $$$5$$$, $$$6$$$, $$$7$$$, $$$8$$$, $$$9$$$, $$$11$$$, $$$22$$$, $$$33$$$, $$$44$$$, $$$55$$$, $$$66$$$, $$$77$$$, $$$88$$$, $$$99$$$, поэтому разрешается вывести любое из них.