Alice 和 Bob 正在玩一个小游戏。桌上有 $n$ 块石头。Alice 和 Bob 轮流捡石头，Alice 先手。每人每次只能捡一块石头，直到所有石头都被捡完。每块石头有两个属性 $A_i$ 和 $B_i$。当 Alice 捡起一块石头时，她获得 $A_i$ 分；当 Bob 捡起一块石头时，他获得 $B_i$ 分。每个人的总分是他们捡起石头时所获得分数的总和。两位玩家都希望最大化自己得分与对方得分的差值，即尽可能使自己的得分减去对方的得分最大。请问 Alice 的得分减去 Bob 的得分的最终结果是多少？

输入格式

第一行包含一个正整数 $T$，表示测试用例的数量，其中 $1 \le T \le 20$。 接下来，对于每个测试用例，重复以下格式： 第一行包含一个正整数 $n$，其中 $1 \le n \le 10^5$。接下来的 $n$ 行包含两个整数 $A_i$ 和 $B_i$，表示第 $i$ 块石头的两个属性。$A_i$ 和 $B_i$ 的值满足 $0 \le A_i, B_i \le 10^9$。

输出格式

对于每个测试用例，输出一行包含一个整数，表示答案。

样例

样例输入 1

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

样例输出 1

1
-1