Migrated from Lutece 175 Ender's Game

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

After Ender had defeated the evil alien which is called bugger by us human, his life become boring. Having played dota for $42$ weeks, he finally realized that the essence of the life is boring.

In order to let the life not so boring any more and make our society harmonious, our wise commander came up with a boring game. Ender caught $n$ buggers in the cage. The $i_{th}$ bugger has two kinds of fight abilities. The attack ability $A_i$ and the defend ability $D_i$. Our cruel Ender wants to let every bugger fight with each other in the cage. Every two buggers in this cage must exactly fight once with each other.

Easily, you can realize that the total number of fights would be exactly $\frac{n\times(n-1)}{2}$. When bugger $i$ fight with bugger $j$, our heart-twisted Ender will gain some happy points whose value is $H_{ij}$ ( $i < j$ ). The happy point can be calculated by the following equation:

$H_{ij}=Max(A_i-A_j, D_i-D_j)-Min(A_i-A_j, D_i-D_j), ( i < j )$

Ender is eagerly want to know the total happy point he can get. As a subaltern of Ender, you must help Ender to calculator it, or you will be fired. You know in this period of economic crisis, a job is so hard to get. So try your best to help Ender.

Input

The first line of the inputs is $T$(no more than $10$), which stands for the number of test cases you need to solve, for each case you must solve it independently and print the answer as the requests.

After $T$, the inputs will be each test case. The first line of each case will be $N$, representing for the number of buggers in the cage（$0 < N\leq 200000$). There will be $N$ lines following. The $i+1_{th}$ line of the input will has two integer $A_i$ and $D_i$, represent the $i_{th}$ bugger's attackability and defend ability. All the values appeared in the input are $32$-bit signed integer.

Output

Please output the answer for all test cases.

Samples

2
3
2 1
1 2
5 3
1
10 1

6
0

Note

The sum of the happy points may be huge and you’d better use long long instead of int. Honor to the great science fiction Ender’s game by Orson Scott Card.

Resources

rectflex