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