CF2204E 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, 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.

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.