A certain business maintains a list of all its customers' names. The list is arranged in order of importance, with the last customer in the list being the most important. Now, he want to create a new list sorted alphabetically according to customers' last names, but among customers with the same last name he want the more important ones to appear earlier in the new list. Alphabetical order (and equality of last names) should not be case sensitive.

Input:- First line contains no. of test cases and first line of each test case contains n i.e. no. of elements and next n lines contains contains a name.

Output:- Print the new list with each element in a new line.