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
"""
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
"""


def print_result(str_arr):
    letter_count_dic = {}

    for i in range(len(str_arr)):
        letter = str_arr[i]

        if letter_count_dic.has_key(letter):
            count = letter_count_dic[letter]
            letter_count_dic[letter] = count + 1
        else:
            letter_count_dic[letter] = 1

    count_letters_dic = {}
    for letter in letter_count_dic.keys():
        count = letter_count_dic[letter]

        if count_letters_dic.has_key(count):
            letters = count_letters_dic[count]
            letters.append(letter)
        else:
            count_letters_dic[count] = [letter]

    counts = list(count_letters_dic.keys())

    counts.sort()

    result_str = ''

    for count in counts:
        letters = count_letters_dic[count]
        letters.sort()

        for letter in letters:
            result_str += letter*count

    print result_str

def run_test():
    n = int(raw_input())

    for i in range(n):
        string_to_sort = str(raw_input())
        print_result(string_to_sort)

run_test()