E. Sum of Digits (and Again)
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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

  1. initially, this string is empty;
  2. then, the decimal representation of the number $$$x$$$ without leading zeros is appended to it on the right;
  3. after that, if $$$x \le 9$$$, the process ends. Otherwise, $$$x$$$ is replaced by the sum of the digits of $$$x$$$, and the process returns to step $$$2$$$;

For example:

  • $$$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 the string $$$S(x)$$$ for some number $$$x$$$, you may leave it unchanged.

Input

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$$$.
Output

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

Example
Input
5
12735
1
011
99999299999999299959999999999999
4621467
Output
75123
1
101
99999999999999999999999999992529
6442167