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

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

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