Statement : Sum of Digits (and Again)

For a positive (strictly greater than $0$) integer $x$, the string $S(x)$ is formed through the following process:

1. Initially, the string is empty.
2. Append to it (on the right) the decimal representation of the number $x$ without leading zeros.
3. If $x \le 9$, the process ends. Otherwise, replace $x$ with the sum of the digits of $x$ and go back to step 2.

Examples:

• $S(75)$ is 75123.
• $S(30)$ is 303.
• $S(9)$ is 9.

You are given a string $s$ consisting of digits. Your task is to rearrange the characters in this string so that it forms the string $S(x)$ for some number $x$. Removing characters and/or adding new characters is not allowed. If the given string $s$ is already equal to $S(x)$ for some number $x$, you may leave it unchanged.

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Each test case consists of one string containing $s$ ($1 \le |s| \le 10^5$) — a sequence of digits.

Additional constraints on the input:

• The sum of lengths of $s$ over all test cases does not exceed $10^5$.
• It is possible to rearrange the digits in $s$ to obtain $S(x)$ for some positive integer $x$.

For each test case, output one string — $s$ after rearranging the characters. If there are multiple valid answers, output any of them.

Input

5
12735
1
011
99999299999999299959999999999999
4621467

Output

75123
1
101
99999999999999999999999999992529
6442167