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

У вас есть строка $$$s$$$, состоящая из цифр от $$$0$$$ до $$$9$$$ включительно. Вы можете произвести над ней следующую операцию любое (возможно нулевое) количество раз:

  • Вы можете выбрать позицию $$$i$$$ и удалить цифру $$$d$$$ на $$$i$$$-й позиции. Затем нужно вставить цифру $$$\min{(d + 1, 9)}$$$ в любую позицию (в начало, в конец или между любыми двумя соседними цифрами).

Какую лексикографически минимальную строку вы можете получить после этих операций?

Строка $$$a$$$ лексикографически меньше строки $$$b$$$ той же длины, если и только если выполняется следующее:

  • в первой позиции, где $$$a$$$ и $$$b$$$ различны, в строке $$$a$$$ находится цифра меньшая, чем соответствующая цифра в $$$b$$$.
Входные данные

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Затем следуют сами наборы входных данных.

Каждый набор входных данных состоит из одной строки, содержащей строку $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$) — строка из цифр. Обратите внимание, что $$$s$$$ это просто строка, состоящая из цифр, поэтому ведущие нули разрешены.

Гарантируется, что сумма длин строки $$$s$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Выведите единственную строку — лексикографически минимальную строку, которую можно получить.

Пример
Входные данные
4
04829
9
01
314752277691991
Выходные данные
02599
9
01
111334567888999
Примечание

В первом наборе входных данных:

  • Удалим $$$8$$$ и поместим в конец строки $$$9$$$. Получается строка $$$04299$$$.
  • Удалим $$$4$$$ и поместим на $$$3$$$-ю позицию строки $$$5$$$. Получается строка $$$02599$$$.

Во втором и третьем наборах входных данных не нужно ничего делать.