Moriarty wants to destroy the Big Ben Clock Tower. In order to do so, he has a lot of strings to form code for activating the bomb. He just want to mess up with his arch-nemesis Mr. Sherlock Holmes. But, on noticing all the strings used to form the code, Moriarty, who's also an insane and a bit OCD kind of a guy, realizes that he does not like the way in which the strings are arranged.

He likes his strings sorted, in a different kind of a way. He wants his strings to be sorted based on the count of characters present in the string. For instance, if the string is: "aaabbc", then the desired string would be: cbbaaa. In case where the count of two characters is same, then the lexicographically smaller one will be printed first. For instance: "aabbcc" then, the output will be: "aabbcc".

Input:

First line of input contains number of test cases T. Each test case contains a single string S.

Output:

For each test cases print the sorted string.

Constraints:

1<=T<=100

1<=|S|<=100

Note:

String contains only lowercase characters ['a' to 'z'].