← 返回题目列表

Codeforces · 2050/D

D. 数字字符串最大化

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

给定一个字符串 $$$s$$$,由从 $$$0$$$ 到 $$$9$$$ 的数字组成。在一次操作中,您可以选择该字符串中的任何数字($$$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

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