题目描述

对于一个正整数 $x$（严格大于 $0$），字符串 $S(x)$ 按以下步骤构造：

1. 初始时，这个字符串为空；
2. 将数字 $x$ 的十进制表示（无前导零）拼接在该字符串的右侧；
3. 如果 $x \le 9$，构造过程结束；否则，把 $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$），表示测试用例的数量。

接下来 $t$ 行，每行输入一个仅由数字组成的字符串 $s$，表示对应的测试用例。

输出格式

对于每个测试用例，输出一行一个字符串，表示重排后的合法字符串。如果存在多个合法的答案，输出其中任意一个即可。

5
12735
1
011
99999299999999299959999999999999
4621467

75123
1
101
99999999999999999999999999992529
6442167

数据规模与约定

对于 $100\%$ 的数据，满足 $1 \le |s| \le 10^5$，所有测试用例的字符串 $s$ 长度之和不超过 $10^5$。

来源

Codeforces Round #1055 (Div. 3) E https://codeforces.com/contest/2204/problem/E