Organize Books

Given several test cases, each containing a list of books, your task is to organize the books according to the following criteria:

• Sort the books by genre in lexicographical (alphabetical) order.
• Within each genre, sort the books by their popularity score in descending order.
• If books have the same popularity score, sort them by their unique identifier in ascending order.

You should output the sorted books for each test case. The books for different genres should be separated by an empty line. If a test case has only one genre, simply output the sorted list for that genre.

The sorting criteria can be formally described using the following ordering rule for a book represented by a triple \((g, id, p)\):

\[ (g_1, id_1, p_1) < (g_2, id_2, p_2) \iff \begin{cases} g_1 p_2, & \text{or}\\ g_1 = g_2 \text{ and } p_1 = p_2 \text{ and } id_1

inputFormat

The input is read from stdin and consists of several lines:

1. The first line contains an integer \(T\) representing the number of test cases.
2. For each test case:
   1. The first line contains an integer \(N\) indicating the number of books in the test case.
   2. The following \(N\) lines each contain a book description in the format: genre book_id popularity_score. Here, genre is a string, while book_id and popularity_score are integers.

outputFormat

The output should be written to stdout and for each test case, it should list the sorted books according to the rules stated above. The books belonging to the same genre are printed consecutively, and different genres are separated by an empty line. There should be no extra spaces or blank lines at the beginning or end of the output.

## sample

2
3
Fantasy 3 90
Science 1 85
Fantasy 2 95
2
Romance 5 80
Romance 3 80

Fantasy 2 95
Fantasy 3 90
Science 1 85
Romance 3 80
Romance 5 80

</p>