Description

Bojack has a list of names from the programming class. He needs to sort the list from the best grades to the lowest in order to know the best and worst student in the class. Help the Bojack to sort the grades! Note that everyone has a unique name, so if they have the same grades, sort it from Z to A. (Not A to Z!)

This is a partial judge program.

Input

The first line consists of an integer T the number of testcases

For each testcase, there is an integer n , the number of students

For the next n line, each line consists of an integer m and string s, representing the grade and name of the student

1 < T < 10

1 < n,m < 50

1 < s < 100000

Output

The lists of students name in descending order.

Sample Input  Download

Sample Output  Download

Partial Judge Code

13744.c

Partial Judge Header

13744.h

Tags

Discuss

Description

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:

1. Uppercase
2. Lowercase
3. Digit

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.

 

Input

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

Output the sorted string in specific order. Dont forget '\n'.

Sample Input  Download

Sample Output  Download

Tags

Discuss