D. A Cruel Segment's Thesis
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$n$$$ segments on a number line. The $$$i$$$-th segment is represented as $$$[l_i, r_i]$$$. Initially, all the segments are unmarked.

You perform the following operation repeatedly until there are no unmarked segments left:

  1. In the $$$k$$$-th operation, if there are at least two unmarked segments, choose any two unmarked segments $$$[l_i, r_i]$$$ and $$$[l_j, r_j]$$$, mark both of them, and add a new marked segment $$$[x_k, y_k]$$$ satisfying the following conditions:
    • $$$l_i \leq x_k \leq r_i$$$,
    • $$$l_j \leq y_k \leq r_j$$$,
    • $$$x_k \leq y_k$$$.
  2. If there is exactly one unmarked segment remaining, mark it.

Your task is to determine the maximum possible sum of lengths of all the marked segments at the end of the process. Note that the length of a segment $$$([l,r])$$$ is $$$r-l$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the number of segments.

Each of the next $$$n$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq 10^9$$$) — the $$$i$$$-th segment.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print a single integer — the maximum possible total length of all marked segments at the end of the process.

Example
Input
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
Output
2999999997
42
59
0
Note

In the first test case, we choose the given two segments and make the new segment $$$[1, 10^9]$$$.

In the second test case, we choose the segments $$$[1, 10]$$$ and $$$[2, 15]$$$ and make the new segment $$$[1,15]$$$. Now, $$$[3, 9]$$$ is the only segment that is left unmarked, and it will be marked in the next step.