Назовём красивым телефонным номером строку из $$$10$$$ цифр, у которой $$$i$$$-я по порядку цифра слева не менее $$$10 - i$$$. То есть первая цифра должна быть хотя бы $$$9$$$, вторая — хотя бы $$$8$$$, $$$\ldots$$$, и последняя — хотя бы $$$0$$$.
Например, 9988776655 — красивый телефонный номер, а 9099999999 — нет, так как вторая цифра, равная $$$0$$$, меньше $$$8$$$.
У Вадима есть красивый телефонный номер. Он хочет переставить его цифры местами таким образом, чтобы получился минимально возможный красивый телефонный номер. Помогите Вадиму решить эту задачу.
Телефонные номера сравниваются как числа.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Единственная строка каждого набора входных данных содержит одну строку $$$s$$$ длины $$$10$$$, состоящую из цифр. Гарантируется, что $$$s$$$ является красивым телефонным номером.
Для каждого набора входных данных выведите единственную строку длины $$$10$$$ — минимально возможный красивый телефонный номер, который Вадим может получить.
49999999999998877665599887766509899999999
9999999999 9876556789 9876567890 9899999999
В первом наборе входных данных для телефонного номера 9999999999, независимо от перестановки цифр, получается один и тот же телефонный номер.
Во втором наборе входных данных для телефонного номера 9988776655 можно доказать, что 9876556789 — это минимальный телефонный номер, который можно получить перестановкой цифр.
| BSUIR Open XIII: Студенческий финал |
|---|
| Закончено |
