CF2050D Digital string maximization

You are given a string $ s $ , consisting of digits from $ 0 $ to $ 9 $ . In one operation, you can pick any digit in this string, except for $ 0 $ or the leftmost digit, decrease it by $ 1 $ , and then swap it with the digit left to the picked. For example, in one operation from the string $ 1023 $ , you can get $ 1103 $ or $ 1022 $ . Find the lexicographically maximum string you can obtain after any number of operations.

The first line of the input consists of an integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. Each test case consists of a single line consisting of a digital string $ s $ ( $ 1 \le |s| \le 2\cdot 10^5 $ ), where $ |s| $ denotes the length of $ s $ . The string does not contain leading zeroes. It is guaranteed that the sum of $ |s| $ of all test cases doesn't exceed $ 2\cdot 10^5 $ .

For each test case, print the answer on a separate line.

In the first example, the following sequence of operations is suitable: $ 19 \rightarrow 81 $ . In the second example, the following sequence of operations is suitable: $ 1709 \rightarrow 1780 \rightarrow 6180 \rightarrow 6710 $ . In the fourth example, the following sequence of operations is suitable: $ 51476 \rightarrow 53176 \rightarrow 53616 \rightarrow 53651 \rightarrow 55351 \rightarrow 55431 $ .