Codeforces Round 861 (Div. 2) |
---|
Закончено |
В этой задаче, в отличие от задачи А, требуется искать наименее удачливый номер, а не наиболее удачливый.
Обратите внимание, что ограничения на эту задачу отличаются от ограничений на задачу А.
В городе Олимп-Сити недавно запустили производство персональных звездолетов. Теперь каждый житель Марса сможет купить себе такое средство передвижения и недорого летать на другие планеты.
Естественно, у каждого звездолета есть номер — некоторое целое положительное число $$$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$$$ строк, по одной строке на каждый набор входных данных, содержащую номер наименее удачливого звездолета в магазине.
Если способов выбрать наименее удачливый номер несколько, то выведите любой из них.
559 6342 4948 5390 901 100
63 44 53 90 1
Рассмотрим первые два набора входных данных.
В пятом тестовом примере наименьшую удачливость имеют числа $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, $$$5$$$, $$$6$$$, $$$7$$$, $$$8$$$, $$$9$$$, $$$11$$$, $$$22$$$, $$$33$$$, $$$44$$$, $$$55$$$, $$$66$$$, $$$77$$$, $$$88$$$, $$$99$$$, поэтому разрешается вывести любое из них.
Название |
---|