我们将电话号码称为 美丽 如果它是 $$$10$$$ 数字的字符串,其中从左边算起第 $$$i$$$ 数字至少是 $$$10 - i$$$。也就是说,第一个数字必须至少为 $$$9$$$,第二个数字至少为 $$$8$$$、$$$\ldots$$$,最后一个数字至少为 $$$0$$$。
例如, 9988776655 是一个漂亮的电话号码,而 9099999999 不是,因为第二个数字 $$$0$$$ 小于 $$$8$$$。
瓦迪姆有一个 美丽 电话号码。他想以这样的方式重新排列它的数字,结果是 最小的可能美丽 电话号码。帮助瓦迪姆解决这个问题。
请注意,电话号码是作为整数进行比较的。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的唯一行包含一个字符串 $$$s$$$,长度为 $$$10$$$,由数字组成。保证 $$$s$$$ 是 美丽 电话号码。
输出
对于每个测试用例,输出一个长度为 $$$10$$$ 的字符串 — Vadim 可以获得的最小可能的漂亮电话号码。
示例
输入复制
49999999999998877665599887766509899999999
输出复制
9999999999 9876556789 9876567890 9899999999
注意
在第一个测试用例中,对于第一个电话号码 9999999999,无论数字如何重新排列,都得到相同的电话号码。
在第二个测试用例中,对于电话号码 9988776655,可以证明 9876556789 是通过重新排列数字可以获得的最小电话号码。