You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

指南针会直接指向星辰。它只能指向八个方向之一：四个主要方向$(N、S、E、W)$或其中的某些组合$(NW、NE、SW、SE)$。否则，它会损坏。指南针可以指向的方向如图所示。

平面上有$n$个不同的整数坐标点。你可以把一个指南针放在一个点上，把一个星辰放在另一个点上，如果指南针可以正确指向星辰，那么指南针就不会坏。请问能有多少种放置指南针和星辰的方式？

输入格式

第一行包含一个整数$t$，表示测试用例的数量。

每个测试用例的第一行包含一个正整数$n$，表示点的数量。

接下来是$n$行，每行包含两个非负整数$x_i,y_i$，表示每个点的坐标，所有点的坐标都是不同的，并且对于所有的$i$，保证$x_i\geq y_i$。

输出格式

对于每个测试用例，输出一个整数，表示不会损坏的指南针点对的数量。

4
3
0 0
2 2
1 1
4
5 4
7 5
9 6
13 10
3
1 1
2 2
0 2
3
4 0
2 1
3 0

6
2
6
4

提示

【样例解释】

第一个测试用例中，任何一对点都不会损坏指南针：

• 指南针在$(0,0)$处，晨星在$(2,2)$处：指南针将指向$NE$。
• 指南针在$(0,0)$处，晨星在$(1,1)$处：指南针将指向$NE$。
• 指南针在$(2,2)$处，晨星在$(0,0)$处：指南针将指向$SW$。
• 指南针在$(2,2)$处，晨星在$(1,1)$处：指南针将指向$SW$。
• 指南针在$(1,1)$处，晨星在$(0,0)$处：指南针将指向$SW$。
• 指南针在$(1,1)$处，晨星在$(2,2)$处：指南针将指向$NE$。

第二个测试用例中，只有两个对点不会损坏指南针：

• 指南针在$(9,6)$处，晨星在$(13,10)$处：指南针将指向$NE$。
• 指南针在$(13,10)$处，晨星在$(9,6)$处：指南针将指向$SW$。

【数据范围】

对于$20\%$的数据，保证$t\leq100,n\leq 10,1\leq x_i,y_i \leq 10^6$。所有点的坐标都是不同的，并且对于所有的$i$，保证$x_i\geq y_i$。

对于$40\%$的数据，保证$t\leq100,n\leq 10^2,1\leq x_i,y_i \leq 10^6$。所有点的坐标都是不同的，并且对于所有的$i$，保证$x_i\geq y_i$。

对于$60\%$的数据，保证$t\leq100,n\leq 10^3,1\leq x_i,y_i \leq 10^6$。所有点的坐标都是不同的，并且对于所有的$i$，保证$x_i\geq y_i$。

对于$100\%$的数据，保证$t\leq100,n\leq 2\cdot10^5,1\leq x_i,y_i \leq 10^6$，同时保证每一个测试点中 $n$的总和不超过 $2\cdot10^5$。所有点的坐标都是不同的，并且对于所有的$i$，保证$x_i\geq y_i$。