G. Good Robot Pathstime limit per test7.5 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputOn a Cartesian plane, there are $$$n$$$ distinct points painted black, while all other points are painted white. Each black point has integer coordinates.There is also a robot that can move one unit in any of the directions 'U' (up), 'D' (down), 'L' (left), or 'R' (right) with a single command.A path of the robot from point $$$p_{1}$$$ to point $$$p_{2}$$$ is a sequence of commands such that if the robot, starting at point $$$p_{1}$$$, executes this sequence, it will arrive at point $$$p_{2}$$$.The shortest path of the robot from point $$$p_{1}$$$ to point $$$p_{2}$$$ is a path whose sequence consists of the minimum possible number of commands.You need to count the number of pairs of points $$$p_i$$$, $$$p_j$$$ ($$$i \neq j$$$) such that for this pair of points the following condition holds:All points with integer coordinates on any shortest path of the robot from point $$$p_{i}$$$ to point $$$p_{j}$$$ are painted black.InputEach test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows. The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^{5}$$$) — the number of points painted black.The next $$$n$$$ lines of each test case contain two integers $$$x_{i}, y_{i}$$$ ($$$-10^{9} \le x_{i}, y_{i} \le 10^{9}$$$) — the coordinates of point $$$p_{i}$$$. All points are pairwise distinct.It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$5 \cdot 10^{5}$$$.OutputFor each test case, output a single integer — the answer to the problem.ExampleInput350 01 00 11 12 0180 0-1 0-2 00 -1-1 -10 11 10 21 22 21 36 -25 -25 -36 -34 -33 -35 -43-100 100-101 99-99 101Output16
70
0
NoteIn the first test case, there are $$$16$$$ suitable pairs of points: $$$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}$$$