Casting

Casting is a manufacturing process in which liquid is poured into a cast (mold) that has a cavity shaped like the object to be produced. The liquid hardens, after which the cast is removed. To mass produce the object by reusing the same cast parts, the cast parts must be removable from the object by translation without destroying either the cast parts or the object.

Given a convex polygon $P$ (the object), we divide the cast into two parts along a straight line through two vertices of $P$. The goal is to choose the two vertices so that both cast parts can each be removed by translation (without destroying the cast parts or the object). For instance, in the original figures, dividing along the line through one pair of vertices lets the upper part be pulled upward and the lower part downward, while dividing along the line through some other pair leaves a part that wraps around the object and cannot be removed in any direction. Thus, not every pair of vertices admits such a division. (Each part may be removed in its own translation direction; removal is not required to be perpendicular to the dividing line.)

Given a convex polygon $P$ with $n$ vertices, write a program that finds all pairs of vertices $(v_i, v_j)$ such that both cast parts of $P$, divided by the straight line through $v_i$ and $v_j$, can be removed by translation.

Your program reads from standard input. The first line contains the number of test cases $T$. Each test case begins with an integer $n$, the number of vertices of a convex polygon $P$, where $3 \le n \le 100{,}000$. The next line contains $2n$ integers $x_1\ y_1\ x_2\ y_2\ \dots\ x_n\ y_n$, where $x_i$ and $y_i$ are the $x$- and $y$-coordinates of vertex $v_i$ of $P$. All coordinates are integers with $-1{,}000{,}000{,}000 \le x_i, y_i \le 1{,}000{,}000{,}000$. The vertices $v_1, v_2, \dots, v_n$ are given in clockwise order along the boundary of $P$.

Your program writes to standard output. For each test case, print a single line containing the number of pairs $(v_i, v_j)$ of vertices with $i < j$ such that both cast parts of $P$, divided by the straight line through $v_i$ and $v_j$, can be removed by translation without destroying either the cast parts or the object.