Bob and Alice

Description

Bob and Alice are planning a trip to \(N\) cities after the final exam. But they don't have any money at all, so they have to do some work to earn money at each city.

Bob knows exactly that, at the \(i\)-th city, they can spend at most \(a_i\) money for fun (definitely they can only spend money on hand and cannot give credit), and then they will work and earn \(b_i\) money. (Note that they'll always have fun first before working.)

Since they want the trip to be fun, they are going to spend as much money as possible.

Now Bob is boasting to Alice. "You know what? I can arrange the order of the cities we visit so that we can enjoy a best trip!'' Of course Alice doesn't believe in Bob because he always brags, and she is right. To avoid getting Alice disappointed again, Bob asks you to help him out.

Input

There are multiple test cases. The first line is an integer \(T\) denoting the number of test cases.

For each test case, the first line is an integer \(N\) (\(1\le N \le 100000\)) indicating the number of cities, and then \(N\) lines follow, each line contains two integer \(a_i\) and \(b_i\) separated by a blank space (\(0\le a_i,b_i \le 10000\)). It is guaranteed that the sum of all \(N\) does not exceed \(5000000\).

Output

For each test case you shall output one line containing one number \(S\), which is the maximum money they can spend if they arrange \(N\) cities in an optimal order.

Sample Case

Input

2
1
1 2
2
1 0
1 1

Output

0
1