I. Big Tournament
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Cats are super cool btw
— CatsAreCool

There are $$$n$$$ players, and these players all participate in a round-robin tournament (that is, each player plays every other player). The $$$i$$$th player has both a magic stat, $$$m_i$$$, and a strength stat, $$$s_i$$$.

For each $$$1 \le i \lt j \le n$$$, the $$$i$$$th and $$$j$$$th players will fight each other. The $$$i$$$th player's advantage over the $$$j$$$th player would be calculated as $$$\max(m_i - m_j, s_i - s_j)$$$. Conversely, the $$$j$$$th player's advantage over the $$$i$$$th player would be $$$\max(m_j - m_i, s_j - s_i)$$$. The winner is the player who has the greatest advantage.

The winning player gets a number of points equal to their advantage over their opponent. If both players have an identical advantage, they tie. Tying players get nothing.

Find the sum of all point totals across the whole tournament.

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.

For each test case: the first line contains a single integer $$$n$$$ $$$(2 \le n \le 10^5)$$$. The next $$$n$$$ lines contain 2 integers, $$$m_i$$$ and $$$s_i$$$ $$$(1 \le m_i, s_i \le 10^9)$$$.

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

—

Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Tests $$$1-2$$$ satisfy $$$n \le 5000$$$.

Test $$$3$$$ satisfies $$$s_i = 1$$$.

Test $$$4$$$ satisfies $$$s_i \le 10$$$

Tests $$$5-20$$$ satisfy no additional constraints.

Output

For each test case, output a single integer — the sum of the point totals of every player after the tournament has concluded.

Example
Input
2
3
3 7
4 4
7 3
5
5 3
8 4
9 1
6 4
12 2
Output
6
33
Note

In the first test case, when the 1st player battles the 2nd player, the 1st player wins and gains 3 points. When the 2nd player battles the 3rd player, the 3rd player wins and gains 3 points. When the 1st player battles the 3rd player, they both have the same advantage (3) so they tie. In total the players earned 3 + 3 = 6 points.