← 返回题目列表

Codeforces · 2098/A

A. 瓦迪姆的收藏

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

我们将电话号码称为 美丽 如果它是 $$$10$$$ 数字的字符串,其中从左边算起第 $$$i$$$ 数字至少是 $$$10 - i$$$。也就是说,第一个数字必须至少为 $$$9$$$,第二个数字至少为 $$$8$$$、$$$\ldots$$$,最后一个数字至少为 $$$0$$$。

例如, 9988776655 是一个漂亮的电话号码,而 9099999999 不是,因为第二个数字 $$$0$$$ 小于 $$$8$$$。

瓦迪姆有一个 美丽 电话号码。他想以这样的方式重新排列它的数字,结果是 最小的可能美丽 电话号码。帮助瓦迪姆解决这个问题。

请注意,电话号码是作为整数进行比较的。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的唯一行包含一个字符串 $$$s$$$,长度为 $$$10$$$,由数字组成。保证 $$$s$$$ 是 美丽 电话号码。

输出

对于每个测试用例,输出一个长度为 $$$10$$$ 的字符串 — Vadim 可以获得的最小可能的漂亮电话号码。

示例

输入
复制

4
9999999999
9988776655
9988776650
9899999999

输出
复制

9999999999
9876556789
9876567890
9899999999

注意

在第一个测试用例中,对于第一个电话号码 9999999999,无论数字如何重新排列,都得到相同的电话号码。

在第二个测试用例中,对于电话号码 9988776655,可以证明 9876556789 是通过重新排列数字可以获得的最小电话号码。