题目描述

我们称一个电话号码为"美丽的"，当它是一个由 $10$ 位数字组成的字符串，且从左数第 $i$ 位数字至少为 $10 - i$。也就是说，第一位数字至少为 $9$，第二位至少为 $8$，$\ldots$，最后一位至少为 $0$。

例如，9988776655 是一个美丽的电话号码，而 9099999999 不是，因为第二位数字是 $0$，小于 $8$。

Vadim 有一个美丽的电话号码。他想要重新排列其中的数字，使得结果是最小的可能的美丽电话号码。请帮助 Vadim 解决这个问题。

请注意，电话号码的比较是按照整数大小进行的。

输入格式

每个测试包含多个测试用例。第一行输入测试用例数量 $t$（$1 \le t \le 10^4$）。接下来是各测试用例的描述。

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

输出格式

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

说明/提示

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

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

翻译由 DeepSeek V3 完成

样例

4
9999999999
9988776655
9988776650
9899999999

9999999999
9876556789
9876567890
9899999999