You are given a list of tasks, each having a deadline and associated profit if completed within the deadline. Each task takes 1 unit of time to complete. What is the maximum profit you can make?

Example:

Tasks (deadline, profit): [(4, 20), (2, 10), (2, 40), (1, 30)]
Output: 90
Explanation: Order of Tasks: 4, 3, 1

Testing

Input Format

The first line contains an integer ‘T’ denoting the number of test cases.

For each test case, the input contains the following lines:

• The first line contains an integer n denoting the number of tasks.
• The next n lines, each have two space-separated integers- deadline_i and profit_i denoting the deadline and profit of each task.

Output Format

One line for each test case, with the maximum profit that can be made.

Sample Input

2
4
4 20
2 10
2 40
1 30
6
2 20
2 40
2 30
1 10
3 50
3 60

Expected Output

90
150

Constraints

1 <= t <= 10
1 <= n <= 2000
1 <= deadlinei, profiti <= 1000