CF1799C.Double Lexicographically Minimum

You are given a string $s$. You can reorder the characters to form a string $t$. Define $t_{\mathrm{max}}$ to be the lexicographical maximum of $t$ and $t$ in reverse order.

Given $s$ determine the lexicographically minimum value of $t_{\mathrm{max}}$ over all reorderings $t$ of $s$.

A string $a$ is lexicographically smaller than a string $b$ if and only if one of the following holds:

• $a$ is a prefix of $b$, but $a \ne b$;
• in the first position where $a$ and $b$ differ, the string $a$ has a letter that appears earlier in the alphabet than the corresponding letter in $b$.

给你一个字符串 $s$。你可以对其中的字符重新排列，得到字符串 $t$。定义 $t_{\mathrm{max}}$ 为 $t$ 与其逆序字符串中字典序较大的那个。

给定 $s$，请在 $s$ 的所有重排 $t$ 中，找出对应的 $t_{\mathrm{max}}$ 的字典序最小值。

当且仅当满足以下条件之一时，字符串 $a$ 的字典序小于字符串 $b$：

• $a$ 是 $b$ 的前缀，但 $a \ne b$；
• 在 $a$ 和 $b$ 首次出现不同字符的位置上，$a$ 中该位置的字母在字母表中早于 $b$ 中对应位置的字母。

The first line contains a single integer $t$ ($1 \leq t \leq 10^5$) — the number of test cases. Descriptions of test cases follow.

The first and only line of each test case contains a string $s$ ($1 \leq |s| \leq 10^5$). $s$ consists of only lowercase English letters.

It is guaranteed that the sum of $|s|$ over all test cases does not exceed $10^5$.

第一行包含一个整数 $t$（$1 \leq t \leq 10^5$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例仅有一行，包含一个字符串 $s$（$1 \leq |s| \leq 10^5$），其中 $s$ 仅由小写英文字母组成。

保证所有测试用例的 $|s|$ 之和不超过 $10^5$。

For each test case print the lexicographically minimum value of $t_{\mathrm{max}}$ over all reorderings $t$ of $s$.

对于每个测试用例，输出字符串 $s$ 的所有重排 $t$ 中，$t_{\mathrm{max}}$ 的字典序最小值。

For the first test case, there is only one reordering of $s$, namely "a".

For the second test case, there are three reorderings of $s$.

• $t = \mathtt{aab}$: $t_{\mathrm{max}} = \max(\mathtt{aab}, \mathtt{baa}) = \mathtt{baa}$
• $t = \mathtt{aba}$: $t_{\mathrm{max}} = \max(\mathtt{aba}, \mathtt{aba}) = \mathtt{aba}$
• $t = \mathtt{baa}$: $t_{\mathrm{max}} = \max(\mathtt{baa}, \mathtt{aab}) = \mathtt{baa}$

The lexicographical minimum of $t_{\mathrm{max}}$ over all cases is "aba".

对于第一个测试用例，字符串 $s$ 只有一种重排，即 "a"。

对于第二个测试用例，字符串 $s$ 共有三种重排：

• $t = \mathtt{aab}$：$t_{\mathrm{max}} = \max(\mathtt{aab}, \mathtt{baa}) = \mathtt{baa}$
• $t = \mathtt{aba}$：$t_{\mathrm{max}} = \max(\mathtt{aba}, \mathtt{aba}) = \mathtt{aba}$
• $t = \mathtt{baa}$：$t_{\mathrm{max}} = \max(\mathtt{baa}, \mathtt{aab}) = \mathtt{baa}$

在所有情况中，$t_{\mathrm{max}}$ 的字典序最小值为 "aba"。