Maximum Subset Sum with Genre Constraint

In a library system, each book is identified by a unique numerical ID and is assigned a genre. Your task is to choose a subset of books in such a way that no two selected books belong to the same genre, and the sum of the book IDs is maximized. In other words, for each genre, you may select at most one book, and you should choose the one with the highest ID if multiple books belong to the same genre.

This can be formally expressed as follows:

Given a list of books with pairs \((id, genre)\), let \(G\) be the set of distinct genres, and for each genre \(g \in G\), let \(x_g\) be the maximum book ID among all books of that genre. The desired result is:

\[ \text{Result} = \sum_{g \in G} x_g \]

For each test case, compute the maximum possible sum under these constraints.

inputFormat

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

• The first line contains an integer T, denoting the number of test cases.
• For each test case:
• The first line contains an integer M, the number of books.
• Then M lines follow, each containing two integers separated by a space: the book ID and the genre ID.

outputFormat

For each test case, output a single line containing the maximum sum of the book IDs such that no two books come from the same genre.

## sample

2
4
100 1
200 2
150 1
120 3
3
50 2
70 2
80 3

470
150

</p>