指南针直接指向晨星。它只能指向八个方向之一:四个基本方向(N、S、E、W)或某种组合(NW、NE、SW、SE)。否则,它会破裂。
指南针可以指向的方向。
平面上有 $$$n$$$ 具有整数坐标的不同点。有多少种方法可以将指南针放在一个地方,而将晨星放在另一个地方,以使指南针不会损坏?
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — 点数。
接下来是 $$$n$$$ 行,每行包含两个整数 $$$x_i$$$, $$$y_i$$$ ($$$-10^9 \leq x_i, y_i \leq 10^9$$$) — 每个点的坐标,所有点都有不同的坐标。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - 不破坏罗盘的点对的数量。
示例
输入 #1
5 3 0 0 -1 -1 1 1 4 4 5 5 7 6 9 10 13 3 -1000000000 1000000000 0 0 1000000000 -1000000000 5 0 0 2 2 -1 5 -1 10 2 11 3 0 0 -1 2 1 -2
输出 #1
6 2 6 8 0
注意
在第一个测试用例中,任何一对点都不会破坏指南针:
- 指南针位于 $$$(0,0)$$$,晨星位于 $$$(-1,-1)$$$:指南针将指向 $$$\text{SW}$$$。
- 指南针位于 $$$(0,0)$$$,晨星位于 $$$(1,1)$$$:指南针将指向 $$$\text{NE}$$$。
- 指南针位于 $$$(-1,-1)$$$,晨星位于 $$$(0,0)$$$:指南针将指向 $$$\text{NE}$$$。
- 指南针位于 $$$(-1,-1)$$$,晨星位于 $$$(1,1)$$$:指南针将指向 $$$\text{NE}$$$。
- 指南针位于 $$$(1,1)$$$,晨星位于 $$$(0,0)$$$:指南针将指向 $$$\text{SW}$$$。
- 指南针位于 $$$(1,1)$$$,晨星位于 $$$(-1,-1)$$$:指南针将指向 $$$\text{SW}$$$。
在第二个测试用例中,只有两对点不会破坏指南针:
- 指南针位于 $$$(6,9)$$$,晨星位于 $$$(10,13)$$$:指南针将指向 $$$\text{NE}$$$。
- 指南针位于 $$$(10,13)$$$,晨星位于 $$$(6,9)$$$:指南针将指向 $$$\text{SW}$$$。