您有一个字符串 $$$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$$$。
在第二个和第三个测试用例中不需要执行任何操作。