Lexicographically Smallest String Transformation

You are given T test cases. In each test case, you are given a string S. Your task is to transform each string into the lexicographically smallest string possible by performing exactly one of the following operations:

• Reverse any contiguous segment of the string.
• Swap any two characters in the string.

Note that if no operation leads to a string that is lexicographically smaller than the original, you may output the original string. The lexicographical order is defined in the usual way (i.e. dictionary order).

Examples:

• For S = "bacd", one valid transformation is to reverse the segment "bac" to get "cabd", but the lexicographically smallest is "abcd".
• For S = "ab", the only possible outputs are "ab" itself (for example by swapping two identical characters) since any operation does not yield a smaller string.
• For S = "zxy", swapping 'z' and 'x' gives "xzy" which is lexicographically smallest.

inputFormat

The first line contains an integer T representing the number of test cases. Each of the following T lines contains a single string S.

outputFormat

For each test case, print the lexicographically smallest string achievable by performing exactly one operation. Each output should be on a new line.

## sample

1
bacd

abcd

</p>