Last name

Time Limit: 2 Seconds    Memory Limit: 65536 KB

For choosing our last names, many of our ancestors didn’t consider its length. For a considerable number of people their last names don'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 last names of its citizens. To do so, government mandates that there should not be any repeated characters in new last names. After announcing this rule, they realized that people started picking the easiest family names such as “a”, “ap”, “bz”, “bd” etc. Thus, they added one more rule to avoid having too many similar family names. The new rule says new last names must contain all different type of characters as their original one and also the order of characters can not be changed. For example, “zanjani” could be changed to “zanji” or “zajni” but not “zanjai” or “jazani” or “bz”.

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

Given last names, for each one find the smallest lexicographical new last 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 consists of small letters of English and its size is less than or equal to 200000.

Output

For each test case, print the smallest possible last name on one line.

Sample Input

3
zanjani
ibrahimovic
hafezshirazi

Sample Output

zajni
brahimovc
afeshirz

Submit

Source: 13th Iran Nationwide Internet Contest - SBU