For a positive (strictly greater than (0)) integer (x), the string (S(x)) is formed through the following process: initially, this string is empty; then, the decimal representation of the number (x) without leading zeros is appended to it on the right; 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. 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.