D. Максимизация цифровой строки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана строка $$$s$$$, состоящая из цифр от $$$0$$$ до $$$9$$$. За одно действие можно выбрать любую цифру, кроме $$$0$$$ или самой левой цифры, уменьшить её на $$$1$$$ и поменять с цифрой слева от неё местами.

Например, за одну операцию из строки $$$1023$$$ можно получить строки $$$1103$$$, $$$1022$$$.

Найдите, какую лексикографически максимальную строку можно получить с помощью этой операции.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$)  — количество наборов входных данных. Далее следует описание наборов входных данных.

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

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

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

Для каждого набора входных данных выведите ответ в единственной строке.

Пример
Входные данные
6
19
1709
11555
51476
9876543210
5891917899
Выходные данные
81
6710
33311
55431
9876543210
7875567711
Примечание

В первом примере подойдёт следующая последовательность операций: $$$19 \rightarrow 81$$$.

Во втором примере подойдёт следующая последовательность операций: $$$1709 \rightarrow 1780 \rightarrow 6180 \rightarrow 6710$$$.

В четвёртом примере подойдёт следующая последовательность операций: $$$51476 \rightarrow 53176 \rightarrow 53616 \rightarrow 53651 \rightarrow 55351 \rightarrow 55431$$$.