CF1730C.Minimum Notation

You have a string $s$ consisting of digits from $0$ to $9$ inclusive. You can perform the following operation any (possibly zero) number of times:

• You can choose a position $i$ and delete a digit $d$ on the $i$-th position. Then insert the digit $\min{(d + 1, 9)}$ on any position (at the beginning, at the end or in between any two adjacent digits).

What is the lexicographically smallest string you can get by performing these operations?

A string $a$ is lexicographically smaller than a string $b$ of the same length if and only if the following holds:

• in the first position where $a$ and $b$ differ, the string $a$ has a smaller digit than the corresponding digit in $b$.

你有一个由数字 $0$ 到 $9$（含）组成的字符串 $s$。你可以执行以下操作任意次（可能为零次）：

• 选择一个位置 $i$，删除第 $i$ 位上的数字 $d$；然后将数字 $\min{(d + 1, 9)}$ 插入到任意位置（字符串开头、结尾，或任意两个相邻数字之间）。

通过执行这些操作，你能得到的字典序最小的字符串是什么？

当且仅当满足以下条件时，字符串 $a$ 的字典序小于长度相同的字符串 $b$：

• 在 $a$ 和 $b$ 首次出现差异的位置上，$a$ 中的数字比 $b$ 中对应位置的数字更小。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then the test cases follow.

Each test case consists of a single line that contains one string $s$ ($1 \le |s| \le 2 \cdot 10^5$) — the string consisting of digits. Please note that $s$ is just a string consisting of digits, so leading zeros are allowed.

It is guaranteed that the sum of lengths of $s$ over all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示测试用例的数量。接下来是各测试用例。

每个测试用例由一行组成，该行包含一个字符串 $s$（$1 \le |s| \le 2 \cdot 10^5$）—— 该字符串仅由数字组成。请注意，$s$ 仅为一个数字字符串，因此允许前导零。

保证所有测试用例中字符串 $s$ 的长度之和不超过 $2 \cdot 10^5$。

Print a single string — the minimum string that is possible to obtain.

输出一个字符串——所能得到的最小字符串。

In the first test case:

• Delete $8$ and insert $9$ at the end of the notation. The resulting notation is $04299$.
• Delete $4$ and insert $5$ in the $3$-rd position of the notation. The resulting notation is $02599$.

Nothing needs to be done in the second and third test cases.

在第一个测试用例中：

• 删除 $8$，并在表示法末尾插入 $9$。得到的表示法为 $04299$。
• 删除 $4$，并在表示法的第 $3$ 个位置插入 $5$。得到的表示法为 $02599$。

第二个和第三个测试用例无需任何操作。