AT_arc209_b [ARC209B] Minimize Even Palindrome

英小文字からなる文字列 $ s $ に対し、 $ s $ の部分文字列であって、偶数長の回文であるものの個数を $ f(s) $ で表します。より厳密には、 $ f(s) $ は以下の条件を全て満たす整数 $ l, r $ の組の個数です。 - $ 1 \leq l \leq r \leq |s| $ - $ r - l + 1 $ は偶数 - $ s_l s_{l+1} \cdots s_{r} $ は回文 英小文字からなる文字列 $ S $ が与えられるので、 $ S $ の文字を並べ替えて得られる文字列 $ S' $ のうち、 $ f(S') $ が最小となるものを $ 1 $ つ出力してください。 $ T $ 個のテストケースが与えられるので、それぞれについて解いてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ 各テストケースは以下の形式で与えられる。 > $ S $

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 番目のテストケースについて、 $ S $ の文字を並べ替えて得られる文字列 $ S' $ のうち、 $ f(S') $ が最小となるものを $ 1 $ つ出力せよ。そのような $ S' $ が複数ある場合は、どれを出力しても正答となる。

### Sample Explanation 1 $ 1 $ 番目のテストケースについて、 $ S $ の文字を並べ替えて得られる文字列 $ S' $ として `see`, `ese`, `ees` が考えられますが、このうち $ f(S') $ が最小となるものは `ese` のみなので、これを出力します。 $ 2 $ 番目のテストケースについて、例えば `xxyxxx` と出力しても正答となります。 ### Constraints - $ 1 \le T \le 10^5 $ - $ 2 \le |S| \le 2 \times 10^5 $ - $ S $ は英小文字からなる - 全てのテストケースにおける $ |S| $ の総和は $ 2 \times 10^5 $ 以下