AT_arc209_b [ARC209B] Minimize Even Palindrome

For a string $ s $ consisting of lowercase English letters, let $ f(s) $ denote the number of substrings of $ s $ that are palindromes of even length. More precisely, $ f(s) $ is the number of pairs of integers $ l, r $ that satisfy all of the following conditions: - $ 1 \leq l \leq r \leq |s| $ . - $ r - l + 1 $ is even. - $ s_l s_{l+1} \cdots s_{r} $ is a palindrome. Given a string $ S $ consisting of lowercase English letters, output one string $ S' $ obtained by rearranging the characters of $ S $ such that $ f(S') $ is minimized. You are given $ T $ test cases. Solve each of them.

The input is given from Standard Input in the following format: > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ Each test case is given in the following format: > $ S $

Output $ T $ lines. The $ i $ -th line should contain one string $ S' $ obtained by rearranging the characters of $ S $ in the $ i $ -th test case such that $ f(S') $ is minimized. If there are multiple such $ S' $ , any of them will be considered correct.

### Sample Explanation 1 For the first test case, the strings $ S' $ obtained by rearranging the characters of $ S $ are `see`, `ese`, and `ees`. Among these, only `ese` minimizes $ f(S') $ , so output it. For the second test case, for example, outputting `xxyxxx` will also be considered correct. ### Constraints - $ 1 \le T \le 10^5 $ - $ 2 \le |S| \le 2 \times 10^5 $ - $ S $ consists of lowercase English letters. - The sum of $ |S| $ over all test cases is at most $ 2 \times 10^5 $ .