В этой задаче, в отличие от задачи А, требуется искать наименее удачливый номер, а не наиболее удачливый.
Обратите внимание, что ограничения на эту задачу отличаются от ограничений на задачу А.
В городе Олимп-Сити недавно запустили производство персональных звездолетов. Теперь каждый житель Марса сможет купить себе такое средство передвижения и недорого летать на другие планеты.
Естественно, у каждого звездолета есть номер — некоторое целое положительное число \(x\). Назовем удачливостью числа \(x\) разность между наибольшей и наименьшей цифрами этого числа. Например, у числа \(142857\) наибольшая цифра равна \(8\), а наименьшая — \(1\), поэтому его удачливость равна \(8-1=7\). А у числа \(111\) все цифры равны \(1\), поэтому его удачливость равна нулю.
Лаксап — известный марсианский блогер, который часто летает в разные уголки Солнечной системы. Чтобы выпускать интересные видео еще быстрее, он решил купить себе звездолет. Придя в магазин, он увидел звездолеты с номерами с \(l\) по \(r\) включительно. Находясь в магазине, Лаксап заинтересовался, какие из звездолетов имеют наименее удачливые номера.
Поскольку звездолетов в магазине много, а Лаксап не умеет программировать, то Вы должны помочь блогеру и написать программу, которая отвечает на его вопрос.
Выходные данные
Выведите \(t\) строк, по одной строке на каждый набор входных данных, содержащую номер наименее удачливого звездолета в магазине.
Если способов выбрать наименее удачливый номер несколько, то выведите любой из них.
Примечание
Рассмотрим первые два набора входных данных.
- удачливость числа \(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\), поэтому разрешается вывести любое из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
59 63
42 49
48 53
90 90
1 100
|
63
44
53
90
1
|