Sort a string in decreasing order based on the frequency of its characters.
If the frequency of characters is the same, sort it according to:
If the frequency of characters is the same as is the same type (either uppercase, lowercase or digits), then sort uppercase and lowecase according to dictionary order, and sort digits with increasing order.
Explanation Sample input 1: 'e' appears twice while 'f' and 'r' both appear once. So 'e' must appear before both 'f' and 'r'. And 'f' is before 'r' since it is dictionary order Explanation Sample input 2: 'b' appears twice while 'a', 'A', '5' and '4' are appear once. So 'b' must appear before both 'a','A','5' and '4'. And Since the order with different type is upercase > lowercase > digit, then 'A' must appear before 'a','5' and '4', and 'a' must appear before '5' and '4'. Finally since '5' and '4' have same frequency then sort it by increasing order.
The first line is an integer T , the number of testcase
Each T lines has a string s
5 < T < 20
1 < length of s < 400
Output the sorted string in specific order. Dont forget '\n'.