D. A Cruel Segment's Thesistime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou 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: 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$$$. 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$$$.InputEach 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$$$.OutputFor each test case, print a single integer — the maximum possible total length of all marked segments at the end of the process.ExampleInput421 10000000001 100000000031 102 153 951 112 715 201 311 1511000000000 1000000000Output2999999997 42 59 0 NoteIn 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.