Lexicographically Smallest FPIS

A Permutation Insensitive String (PIS) is a string which does not change even if the positions of the characters are interchanged. For example, if the value of a PIS is ‘abc’ it can also be written as ‘acb’, ‘bca’ etc. A Frequency Insensitive String (FIS) is a string whose value does not change if the frequency of any character is increased or decreased (Without altering the total length and without removing any character completely). So if the value of an FIS is ‘aabc’ it can also be ‘abbc’, or ‘abcc’. An FPIS (Frequency and Permutation Insensitive String) is a string that is both permutation and frequency insensitive. Given an FPIS you will have to write the lexicographically smallest version of it. Input First line of the input file contains an integer T (T ≤ 1000) which denotes how many strings to follow. Each of the next T lines contains a single FPIS containing at most 1000 characters. All these characters are from lower case English alphabet. Output For each string in the input produce one line of output. This line contains lexicographically smallest version of the input FPIS. The way you find lexicographic order is:

1. Compare the first (Leftmost) character of both strings. If they are different, order is given by the order of the two characters. (‘a’ is less than ‘b’, ‘y’ is (usually) less than ‘z’)
2. If they are the same, move on to the next character of both strings.
3. If you run out of characters in one of the strings, that one comes first.
4. If you run out of characters in both strings, they are equal. Sample Input 4 bca pqab aabb c Sample Output abc abpq aaab c