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
def unique(my_list):
    list_ip=[]
    for i in my_list:
        if i not in list_ip:
            list_ip.append(i)
    return list_ip




import sys
s=[]
for line in sys.stdin:
    s.append(line)
for y in range(0,len(s)):
    s[y]=s[y].rstrip('\n')
for i in range(1,int(s[0])+1):
    dict_count={}
    temp=list(s[i])
    temp=sorted(temp)
    list_unique=unique(temp)
    for j in list_unique:
        count=0
        for k in temp:
            if j==k:
                count=count+1
        dict_count[j]=count
    temp=sorted(dict_count.values())
    temp_2=sorted(dict_count.keys())
    u=1
    list_fin=[]
    while u<max(temp)+1:
        for key in temp_2:
            if dict_count[key]==u:
                for t in range(1,u+1):
                    list_fin.append(key)
        u=u+1
    a=''.join(list_fin)
    print a