a-b Problem

Problem Description

Alice and Bob are playing a little game. There are $n$ stones. Alice and Bob take turns picking stones, with Alice going first. Each person can only pick one stone at a time until all the stones are gone. Each stone has two attributes, $A_i$ and $B_i$. When Alice picks a stone, she earns $A_i$ points, and when Bob picks a stone, he earns $B_i$ points. The total score for each person is the sum of the points they earn when picking a stone. Both players want to maximize the difference between their scores, aiming to have their own score minus the opponent's score as large as possible. The question is, what is the final result of Alice's score minus Bob's score?

Input

The first line contains a positive integer, $T$, representing the number of test cases, where $1 ≤ T ≤ 20$. Next, for each test case, the following format is repeated: The first line contains a positive integer, $n$, where $1 ≤ n ≤ 10^5$. The next $n$ lines contain two integers, $A_i$ and $B_i$, representing the two attributes of the ith stone. The values of $A_i$ and $B_i$ satisfy $0 ≤ A_i, B_i ≤ 10^9$.

Output

For each test case, output one line containing an integer representing the answer.

Sample Input

2
3
0 2
1 2
3 3
3
1 0
2 3
0 4

Sample Output

1
-1

Source

2023“钉耙编程”中国大学生算法设计超级联赛（4）