G. 好机器人路径

时间限制： 每测试 $7.5$ 秒
内存限制： 每测试 $512$ 兆字节

在一个笛卡尔平面上，有 $n$ 个不同的点被涂成黑色，而所有其他点被涂成白色。每个黑色点具有整数坐标。

还有一个机器人，通过一条命令可以向任意方向移动一个单位：'U'（上）、'D'（下）、'L'（左）或 'R'（右）。

机器人从点 $p_1$ 到点 $p_2$ 的一条路径是一个命令序列，使得机器人从点 $p_1$ 开始执行该序列后，将到达点 $p_2$。

机器人从点 $p_1$ 到点 $p_2$ 的最短路径是其命令序列由最少可能数量的命令组成的路径。

你需要统计满足以下条件的点对 $(p_i, p_j)$（$i \neq j$）的数量：

机器人从点 $p_i$ 到点 $p_j$ 的任意一条最短路径上的所有整数坐标点都被涂成黑色。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ $(1 \leq t \leq 10^4)$。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ $(1 \leq n \leq 5 \cdot 10^5)$ — 黑色点的数量。

接下来 $n$ 行，每行包含两个整数 $x_i, y_i$ $(-10^9 \leq x_i, y_i \leq 10^9)$ — 点 $p_i$ 的坐标。所有点两两不同。

保证所有测试用例的 $n$ 之和不超过 $5 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数 — 问题的答案。

样例

输入

3
5
0 0
1 0
0 1
1 1
2 0
18
0 0
-1 0
-2 0
0 -1
-1 -1
0 1
1 1
0 2
1 2
2 2
1 3
6 -2
5 -2
5 -3
6 -3
4 -3
3 -3
5 -4
3
-100 100
-101 99
-99 101

输出

16
70
0

样例解释

在第一个测试用例中，有 $16$ 对合适的点：

• $(p_1, p_2)$
• $(p_1, p_3)$
• $(p_1, p_4)$
• $(p_1, p_5)$
• $(p_2, p_1)$
• $(p_2, p_3)$
• $(p_2, p_4)$
• $(p_2, p_5)$
• $(p_3, p_1)$
• $(p_3, p_2)$
• $(p_3, p_4)$
• $(p_4, p_1)$
• $(p_4, p_2)$
• $(p_4, p_3)$
• $(p_5, p_1)$
• $(p_5, p_2)$

注意：$(p_3, p_5)$ 不是合适的点对，因为从 $(0, 1)$ 到 $(2, 0)$ 存在一条最短路径经过了白色点 $(2, 1)$（该点不在黑色点集合中）。