← 返回题目列表

Codeforces · 1730/C

C. 最小符号

中文机器翻译题面 查看原题

您有一个字符串 $$$s$$$,由从 $$$0$$$ 到 $$$9$$$ 的数字组成。您可以执行以下操作任意次(可能为零):

- 您可以选择一个位置$$$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 \cdot 10^5$$$) — 由数字组成的字符串。请注意,$$$s$$$ 只是一个由数字组成的字符串,因此允许使用前导零。

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

输出

打印单个字符串 — 可以获得的最小字符串。

示例

输入 #1

4
04829
9
01
314752277691991

输出 #1

02599
9
01
111334567888999

注意

在第一个测试用例中:

- 删除 $$$8$$$ 并在符号末尾插入 $$$9$$$。结果符号为 $$$04299$$$。
- 删除 $$$4$$$ 并在符号的 $$$3$$$-rd 位置插入 $$$5$$$。结果符号为 $$$02599$$$。

在第二个和第三个测试用例中不需要执行任何操作。