题目描述

数轴上有 $n$ 个人，第 $i$ 个人起始于点 $a_i$，目标到达点 $b_i$。对于每个人，都有 $a_i < b_i$，并且所有人的起点和终点都互不相同（即 $2n$ 个数 $a_1, a_2, \dots, a_n, b_1, b_2, \dots, b_n$ 都各不相同）。

所有人会同时以每秒 $1$ 单位的速度出发，直至到达各自的终点 $b_i$。当两个人在同一个点相遇时，他们会互相打招呼一次。请问总共会有多少次打招呼？

注意，即使某个人已经到达终点，他仍然可以和其他人打招呼。

输入格式

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示人数。

接下来 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$-10^9 \leq a_i < b_i \leq 10^9$），表示每个人的起点和终点。

对于每个测试用例，所有 $2n$ 个数 $a_1, a_2, \dots, a_n, b_1, b_2, \dots, b_n$ 都互不相同。

所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示会发生多少次打招呼。

样例

5
2
2 3
1 4
6
2 6
3 9
4 5
1 8
7 10
-2 100
4
-10 10
-5 5
-12 12
-13 13
5
-4 9
-2 5
3 4
6 7
8 10
4
1 2
3 4
5 6
7 8

1
9
6
4
0

样例说明

在第一个测试用例中，两个人会在点 $3$ 相遇并互相打招呼。

由 ChatGPT 4.1 翻译

来源

Codeforces 1915F，英文题名 Greetings。