CF2050D Digital string maximization

给你一个由 $0$ 至 $9$ 的数字组成的字符串 $s$ 。在一次运算中，您可以选取该字符串中除 $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$ 。

对于每个测试用例，在单独一行中打印其对应的答案。 ## 样例 #1 ### 样例输入 #1 ``` 6 19 1709 11555 51476 9876543210 5891917899 ``` ### 样例输出 #1 ``` 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$ .

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 $ .