CF1730C Minimum Notation

你有一个只包含数字 $0$ 到 $9$ 的字符串 $s$。你可以进行如下操作任意次（也可以不进行）： - 你可以选择一个位置 $i$，删除第 $i$ 位上的数字 $d$，然后将数字 $\min(d+1, 9)$ 插入到任意位置（可以是开头、结尾或任意两个相邻数字之间）。 通过进行这些操作，你能得到的字典序最小的字符串是什么？ 对于长度相同的字符串 $a$ 和 $b$，如果在第一个不同的位置，$a$ 的数字比 $b$ 的对应数字小，则称 $a$ 的字典序小于 $b$。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来每个测试用例包含一行，一个只包含数字的字符串 $s$（$1 \le |s| \le 2 \times 10^5$）。请注意，$s$ 只是一个数字字符串，允许前导零。 保证所有测试用例中 $s$ 的总长度不超过 $2 \times 10^5$。

输出一行，表示通过操作可以得到的字典序最小的字符串。

在第一个测试用例中： - 删除 $8$ 并将 $9$ 插入到末尾，得到 $04299$。 - 删除 $4$ 并将 $5$ 插入到第 $3$ 位，得到 $02599$。 在第二个和第三个测试用例中，无需进行任何操作。 由 ChatGPT 4.1 翻译