对于正整数(严格大于 $$$0$$$)$$$x$$$,字符串 $$$S(x)$$$ 通过以下过程形成:
- 最初,该字符串为空;
- 然后,将不带前导零的数字 $$$x$$$ 的十进制表示形式附加到其右侧;
- 之后,如果$$$x \le 9$$$,则过程结束。否则,将$$$x$$$替换为$$$x$$$的各位数字之和,并返回步骤$$$2$$$;
例如:
- $$$S(75)$$$ 是 75123;
- $$$S(30)$$$ 是 303;
- $$$S(9)$$$ 是 9.
给你一个由数字组成的字符串 $$$s$$$。您的任务是重新排列该字符串中的字符,使其形成某个数字 $$$x$$$ 的字符串 $$$S(x)$$$。不允许删除字符和/或添加新字符。如果给定的字符串 $$$s$$$ 已经是某个数字 $$$x$$$ 的字符串 $$$S(x)$$$,则可以将其保持不变。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例由一个字符串组成,其中包含 $$$s$$$ ($$$1 \le |s| \le 10^5$$$) — 一系列数字。
输入的附加限制:
- 所有测试用例$$$s$$$的长度总和不超过$$$10^5$$$;
- 可以重新排列 $$$s$$$ 中的数字以获得某个正整数 $$$x$$$ 的 $$$S(x)$$$。
输出
对于每个测试用例,重新排列字符后输出一个字符串 - $$$s$$$。如果有多个有效答案,则输出其中任何一个。
示例
输入复制
5127351011999992999999992999599999999999994621467
输出复制
751231101999999999999999999999999999925296442167