{"raw_statement":[{"iden":"problem statement","content":"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:\n\n*   $1 \\leq l \\leq r \\leq |s|$.\n*   $r - l + 1$ is even.\n*   $s_l s_{l+1} \\cdots s_{r}$ is a palindrome.\n\nGiven 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.\nYou are given $T$ test cases. Solve each of them."},{"iden":"constraints","content":"*   $1 \\le T \\le 10^5$\n*   $2 \\le |S| \\le 2 \\times 10^5$\n*   $S$ consists of lowercase English letters.\n*   The sum of $|S|$ over all test cases is at most $2 \\times 10^5$."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$T$\n$\\text{case}_1$\n$\\text{case}_2$\n$\\vdots$\n$\\text{case}_T$\n\nEach test case is given in the following format:\n\n$S$"},{"iden":"sample input 1","content":"3\nsee\nxxxxxy\nabracadabra"},{"iden":"sample output 1","content":"ese\nxxxyxx\nabracadabra\n\nFor 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.\nFor the second test case, for example, outputting `xxyxxx` will also be considered correct."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}