You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

一个 10 位数字学号称为美丽学号： 第 $i$ 位数字至少为 $10-i$

• 第1位 ≥9
• 第2位 ≥8
• 第3位 ≥7
• ……
• 第10位 ≥0

给定一个合法的美丽学号（10位数字串），可以重新排列所有数字，求重排后字典序最小、且仍然是美丽学号的 10 位数字串。

输入格式

第一行：整数 $t(1 \le t \le 10^4)$ 表示测试用例数。 每行一个长度为 10 的数字字符串，保证输入一定是美丽学号。

输出格式

每组输出一个 10 位数字字符串，为满足条件的最小学号。

输入输出样例

输入

4
9999999999
9988776655
9988776650
9899999999

输出

9999999999
9876556789
9876567890
9899999999

数据范围

$1 \le t \le 10^4$