数轴上给出了 $$$n$$$ 线段。第 $$$i$$$ 段表示为 $$$[l_i, r_i]$$$。最初,所有段都是 未标记.
重复执行以下操作,直到没有剩余未标记的段:
- 在第 $$$k$$$ 次操作中,如果至少有两个未标记段,则选择任意两个未标记段 $$$[l_i, r_i]$$$ 和 $$$[l_j, r_j]$$$, 标记两者,并添加 新标记 段$$$[x_k, y_k]$$$满足以下条件:
- $$$l_i \leq x_k \leq r_i$$$,
- $$$l_j \leq y_k \leq r_j$$$,
- $$$x_k \leq y_k$$$。
- 如果只剩下一个未标记的段, 标记它.
您的任务是确定流程结束时所有标记段的最大可能长度总和。请注意,段 $$$([l,r])$$$ 的长度为 $$$r-l$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 段数。
接下来的 $$$n$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq 10^9$$$) — 第 $$$i$$$ 段。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 过程结束时所有标记段的最大可能总长度。
示例
输入复制
421 10000000001 100000000031 102 153 951 112 715 201 311 1511000000000 1000000000
输出复制
2999999997 42 59 0
注意
在第一个测试用例中,我们选择给定的两个段并将新段设置为 $$$[1, 10^9]$$$。
在第二个测试用例中,我们选择段 $$$[1, 10]$$$ 和 $$$[2, 15]$$$ 并创建新段 $$$[1,15]$$$。现在,$$$[3, 9]$$$ 是唯一未标记的段,它将在下一步中被标记。