C. Double Lexicographically Minimumtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou 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. InputThe 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.OutputFor each test case print the lexicographically minimum value of t_{\mathrm{max}} over all reorderings t of s. ExampleInput
12aaababbabcaabbaabbbaaabbabbbabbbbabbcceagaffcabaOutput
a
aba
bab
bca
abba
abbba
ababa
bbab
bbabb
bbcca
agea
acffba
NoteFor 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". 
12aaababbabcaabbaabbbaaabbabbbabbbbabbcceagaffcaba
a aba bab bca abba abbba ababa bbab bbabb bbcca agea acffba 
['greedy', 'strings', '*1700']