Rearrange String by Frequency

You are given a string and your task is to rearrange its characters based on their frequency. The characters should be ordered in descending order of frequency. If two characters have the same frequency, they should be arranged in lexicographical (alphabetical) order.

Note: All characters (including uppercase and lowercase) are treated as distinct.

The problem can be formally defined as follows:

Given a string \(S\) of length \(n\), let \(f(c)\) denote the frequency of character \(c\) in \(S\). You are required to construct a new string \(S'\) such that if \(c_1\) and \(c_2\) are two characters in \(S'\) with frequencies \(f(c_1)\) and \(f(c_2)\) respectively, then either \(f(c_1) > f(c_2)\) or \(f(c_1) = f(c_2)\) and \(c_1 < c_2\) in lexicographical order.

Implement the solution to read from standard input and write to standard output.

inputFormat

The input is read from standard input and has the following format:

T
s_1
s_2
...
s_T

Here:

• T: Integer representing the number of test cases.
• s_i: A non-empty string for the i-th test case.

outputFormat

For each test case, output the rearranged string on a new line. The rearranged string is formed by ordering the characters of the input string by descending frequency; if frequencies are equal then by lexicographical order.

## sample

1
tree

eert

</p>