Little Ashish got a lot of strings as his birthday gift. He does not mind getting so many strings for free; in fact, he loves them. But, on noticing all the strings he received as a gift, Little Ashish, who's also a snob 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']. 

SAMPLE INPUT
3
aabbccdd
aabcc
hackerearthSAMPLE OUTPUT
aabbccdd
baacc
cktaaeehhrr
num_cases = int(raw_input().rstrip("\n"))
for i in range(num_cases):
    input = raw_input().rstrip("\n")

    dictionary = {}
    for x in input:
        if (dictionary.__contains__(x)):
            dictionary[x] = dictionary[x] + 1
        else:
            dictionary[x] = 1

    lex_sorted_list = sorted(dictionary.items(), key = lambda t : t[0])
    freq_sorted_list = sorted(lex_sorted_list, key = lambda t : t[1])
    out = []
    for tup in freq_sorted_list:
   	    for x in range(tup[1]):
   	    	out.append(tup[0])
    
    print "".join(out)