AT_arc209_b [ARC209B] Minimize Even Palindrome

对于一个仅由小写英文字母组成的字符串 $s$，令 $f(s)$ 表示 $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')$ 最小。 你将会得到 $T$ 组测试数据。请分别求解。

输入从标准输入读取，格式如下： > $T$ $\text{case}_1$ $\text{case}_2$ $\vdots$ $\text{case}_T$ 每组测试数据格式如下： > $S$

输出共 $T$ 行。 第 $i$ 行输出一行字符串，为通过重新排列 $S$ 得到的某一个 $S'$，使得 $f(S')$ 最小。如果有多个满足要求的 $S'$，输出其中任意一个均可。

### 样例解释 1 对于第一组测试数据，$S$ 的所有排列结果为 `see`、`ese`、`ees`。其中，只有 `ese` 能使 $f(S’)$ 最小，因此输出它。 对于第二组测试数据，例如输出 `xxyxxx` 也是符合条件的。 ### 约束条件 - $1 \leq T \leq 10^5$ - $2 \leq |S| \leq 2 \times 10^5$ - $S$ 仅包含小写英文字母。 - 所有测试数据中 $|S|$ 的和不超过 $2 \times 10^5$。 由 ChatGPT 5 翻译