First name

Time Limit: 3 Seconds    Memory Limit: 65536 KB

For choosing our first names, many of our ancestors didn’t consider its length. For a considerable number of people their first name doesn’t fit on their passports or bank cards. Sometimes they have to change them or make them shorter. 

Recently one of the governments decided to shorten all first names of its citizens. To do so, government mandates that there should not be any repeated characters in new first names. After announcing this rule, they realized that people started picking the easiest first names such as “ya”, “sh”, “f”, “ir” etc. Thus, they added one more rule to avoid having too many similar first names. The new rule says new first names must contain all different type of characters as their original one and also the order of characters cannot be changed. For example, “babak” could be changed to “bak” but not “abak” or “kabab” or “bz”.

After announcing these rules, people started thinking to how to change their first name in order to have the smallest lexicographical possible one.

Given first names, for each one find the smallest lexicographical new first name based on aforementioned rules.

Input

In first line of input there is T, number of test cases.

For each test case, there is one line of input which contains string S which constists of small letters of English and its size is less than 20.

Output

Foe each test case, print the smallest possible first name on one line.

Sample Input

3
babak
zelatan
khajeshamsoddin

Sample Output

abk
zelatn
kajehmsodin

Submit

Source: 13th Iran Nationwide Internet Contest - SBU