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 printString(keys, values):
    stringList = []
    for i in xrange(0, len(keys)):
        for j in xrange(0, values[i]):
            stringList.append(keys[i])
    print "".join(stringList)

T = raw_input("")
T = int(T)

if T < 1 or T > 100:
    exit()

for i in range(0, T):
    S = raw_input("")
    length = len(S)
    if length < 1 or length > 100:
       exit()

    charDictionary = {}
    for c in S:
        if c in charDictionary:
            charDictionary[c] += 1
        else:
            charDictionary[c] = 1

    keys = []
    values = []
    for key,value in charDictionary.items():
        keys.append(key)
        values.append(value)

    for j in xrange(0, len(keys)):
        for k in xrange(j+1, len(keys)):
            if values[j] > values[k]:
                tmp = values[j]
                values[j] = values[k]
                values[k] = tmp

                tmp = keys[j]
                keys[j] = keys[k]
                keys[k] = tmp

            elif values[j] == values[k] and keys[j] > keys[k]:
                tmp = keys[j]
                keys[j] = keys[k]
                keys[k] = tmp
    
    printString(keys, values)