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

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

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