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
__author__ = 'vivekanand'

t = int(raw_input())


for i in range(0,t):

    _str = raw_input()
    ascii_list = []
    runs = {}

    set_str = set(_str)
    num_list = []
    for each_char in set_str:
        num_list.append(_str.count(each_char))
        _n = str(_str.count(each_char))
        if not (runs.has_key(_n)):
            runs[_n] = [ord(each_char)]

        else:
            runs[_n].append(ord(each_char))



    output_list = ""
    for each_num in sorted(set(num_list)):
        if len(runs[str(each_num)]) > 1:
            for each_ascii in sorted(runs[str(each_num)]):
                for j in range(0 , each_num):
                    output_list = output_list + chr(each_ascii)
        else:
            for j in range(0,each_num):
                    output_list = output_list + chr(runs[str(each_num)][0])



    print output_list