Lexicographically Smallest String

You are given a string s. You can perform the following operation any number of times: select any substring of s and reverse it. Prove that by applying these operations, the lexicographically smallest string you can obtain is the string with its characters sorted in increasing order.

In mathematical terms, if we denote the sorted version of the string s as \(\text{sorted}(s)\), then the answer for each test case is \(\text{sorted}(s)\). For example, for \(s = \texttt{cba}\), the smallest possible string is \(\texttt{abc}\).

Your task is to output the lexicographically smallest string (i.e. the sorted string) for each provided test case.

inputFormat

The first line contains an integer T representing the number of test cases. Each of the following T lines contains a non-empty string s consisting of lowercase English letters.

outputFormat

For each test case, output a single line containing the lexicographically smallest string obtainable from s by reversing any substring any number of times. This is equivalent to outputting the sorted characters of s.

1
cba

abc