给定一个字符串 $$$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$$$。