数轴上给定 $n$ 条线段，第 $i$ 条线段表示为 $[l_i,r_i]$。 初始时所有线段均为未标记状态。

你重复执行以下操作，直到不存在未标记的线段：

在第 $k$ 次操作中：

1. 若剩余至少两条未标记线段： 任选两条未标记线段 $[l_i,r_i]$、$[l_j,r_j]$，将两条都标记； 同时新增一条已标记线段 $[x_k,y_k]$，满足：$$l_i \le x_k \le r_i,\quad l_j \le y_k \le r_j,\quad x_k \le y_k $$
2. 若只剩恰好一条未标记线段，直接将它标记。

定义线段 $[l,r]$ 的长度为 $r-l$。 求最终所有被标记线段的长度总和的最大可能值。

输入格式

多组测试用例。 第一行输入整数 $t$（$1\le t\le 10^4$），表示测试组数。

每组测试用例： 第一行输入整数 $n$（$1\le n\le 2\cdot 10^5$），表示线段数量。 接下来 $n$ 行，每行两个整数 $l_i,r_i$（$1\le l_i\le r_i\le 10^9$），代表一条线段。

保证所有测试用例的 $n$ 总和不超过 $2\cdot 10^5$。

输出格式

对每组测试用例，输出一个整数：所有标记线段长度总和的最大可能值。

样例输入

4
2
1 1000000000
1 1000000000
3
1 10
2 15
3 9
5
1 11
2 7
15 20
1 3
11 15
1
1000000000 1000000000

样例输出

2999999997
42
59
0

样例说明

1. 第一组：选取两条给定线段，构造新线段 $[1,10^9]$，得到最大总长。
2. 第二组：先合并 $[1,10]$ 与 $[2,15]$ 构造出新线段 $[1,15]$； 最后剩余单独线段 $[3,9]$ 直接标记。
3. 第四组：只有一条线段，长度为 $10^9-10^9=0$，故输出 $0$。