Дана строка \(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\).
Для каждого набора входных данных выведите ответ в единственной строке.
В первом примере подойдёт следующая последовательность операций: \(19 \rightarrow 81\).
Во втором примере подойдёт следующая последовательность операций: \(1709 \rightarrow 1780 \rightarrow 6180 \rightarrow 6710\).
В четвёртом примере подойдёт следующая последовательность операций: \(51476 \rightarrow 53176 \rightarrow 53616 \rightarrow 53651 \rightarrow 55351 \rightarrow 55431\).
6 19 1709 11555 51476 9876543210 5891917899
81 6710 33311 55431 9876543210 7875567711
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач