CF1530E.Minimax

Prefix function of string $t = t_1 t_2 \ldots t_n$ and position $i$ in it is defined as the length $k$ of the longest proper (not equal to the whole substring) prefix of substring $t_1 t_2 \ldots t_i$ which is also a suffix of the same substring.

For example, for string $t = $ abacaba the values of the prefix function in positions $1, 2, \ldots, 7$ are equal to $[0, 0, 1, 0, 1, 2, 3]$.

Let $f(t)$ be equal to the maximum value of the prefix function of string $t$ over all its positions. For example, $f($abacaba$) = 3$.

You are given a string $s$. Reorder its characters arbitrarily to get a string $t$ (the number of occurrences of any character in strings $s$ and $t$ must be equal). The value of $f(t)$ must be minimized. Out of all options to minimize $f(t)$, choose the one where string $t$ is the lexicographically smallest.

字符串 $t = t_1 t_2 \ldots t_n$ 在位置 $i$ 处的前缀函数定义为：子串 $t_1 t_2 \ldots t_i$ 的最长真前缀（即不等于该子串自身的前缀）的长度 $k$，且该前缀同时也是该子串的一个后缀。

例如，对字符串 $t = $ abacaba，其在位置 $1, 2, \ldots, 7$ 处的前缀函数值分别为 $[0, 0, 1, 0, 1, 2, 3]$。

令 $f(t)$ 表示字符串 $t$ 在所有位置上的前缀函数值的最大值。例如，$f($abacaba$) = 3$。

现给定一个字符串 $s$。你可以任意重排其字符，得到字符串 $t$（即 $s$ 与 $t$ 中每个字符的出现次数必须完全相同）。要求使 $f(t)$ 尽可能小；在所有能使 $f(t)$ 取得最小值的方案中，选择字典序最小的字符串 $t$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). Description of the test cases follows.

The only line of each test case contains string $s$ ($1 \le |s| \le 10^5$) consisting of lowercase English letters.

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^5$）。随后是测试用例的描述。

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

保证所有测试用例中字符串 $s$ 的长度总和不超过 $10^5$。

For each test case print a single string $t$.

The multisets of letters in strings $s$ and $t$ must be equal. The value of $f(t)$, the maximum of prefix functions in string $t$, must be as small as possible. String $t$ must be the lexicographically smallest string out of all strings satisfying the previous conditions.

对每个测试用例，输出一个字符串 $t$。

字符串 $s$ 和 $t$ 中字母的多重集合必须相等。$t$ 的函数值 $f(t)$（即字符串 $t$ 的所有前缀函数值中的最大值）必须尽可能小。在满足前述条件的所有字符串中，$t$ 必须是字典序最小的字符串。

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$.

In the first test case, $f(t) = 0$ and the values of prefix function are $[0, 0, 0, 0, 0]$ for any permutation of letters. String ckpuv is the lexicographically smallest permutation of letters of string vkcup.

In the second test case, $f(t) = 1$ and the values of prefix function are $[0, 1, 0, 1, 0, 1, 0]$.

In the third test case, $f(t) = 5$ and the values of prefix function are $[0, 1, 2, 3, 4, 5]$.

字符串 $a$ 在字典序上小于字符串 $b$，当且仅当以下条件之一成立：

• $a$ 是 $b$ 的前缀，但 $a \ne b$；
• 在 $a$ 与 $b$ 首次出现差异的位置上，$a$ 中的字母在字母表中位于 $b$ 中对应字母之前。

在第一个测试用例中，$f(t) = 0$，且对于字母的任意排列，其前缀函数值均为 $[0, 0, 0, 0, 0]$。字符串 ckpuv 是字符串 vkcup 的字母所构成的所有排列中字典序最小的一个。

在第二个测试用例中，$f(t) = 1$，其前缀函数值为 $[0, 1, 0, 1, 0, 1, 0]$。

在第三个测试用例中，$f(t) = 5$，其前缀函数值为 $[0, 1, 2, 3, 4, 5]$。