Lexicographical Minimal String

Given a list of strings, for each string, sort its characters in ascending order to produce the lexicographically smallest possible string.

For example, given the string banana, the sorted order is aaabnn.

In mathematical terms, if ( s = s_1s_2\ldots s_n ) is a string, then the answer is the sorted permutation of ( s ), that is, ( s' = sort(s) ) which is the lexicographically smallest string obtainable from ( s ).

This solution typically requires ( O(n \log n) ) time complexity per string due to the sorting operation.

inputFormat

The first line of input contains an integer ( T ) representing the number of queries. Each of the next ( T ) lines contains a non-empty string.

outputFormat

For each query, output the lexicographically smallest string after sorting its characters. Each output should be printed on a new line.## sample

3
dcba
banana
abcdefg

abcd
aaabnn
abcdefg