Convex Polygon MST

There is a convex polygon with $n$ vertices on a plane. Let $V$ be the set of its vertices. Remove all the edges of the polygon, and then create a tree with $n$ vertices by repeating the following operation $n-1$ times:

• Select two distinct vertices $x, y \in V$. Add an edge between $x$ and $y$. If the Euclidean distance between $x$ and $y$ is $d(x,y)$, you gain $(d(x,y))^2$ points.

Find the maximum possible total score from the $n-1$ operations.

The input file contains multiple test cases. The first line contains an integer $t$, the number of test cases. Then $t$ test cases follow, each in the following format.

$n$

$x_1$ $y_1$ ⋮ $x_n$ $y_n$

$n$ is the number of vertices, with $3 \le n \le 120\,000$. The sum of all $n$ values in one input file is at most $120\,000$. $x_i$ and $y_i$ are the coordinates of the $i$-th vertex, and each coordinate is an integer from $-10^9$ to $10^9$. The vertices are given in counterclockwise order as seen from the centroid of the convex polygon. No three distinct vertices of the convex polygon lie on a single line.

Print the maximum possible total score from the $n-1$ operations.

The Euclidean distance between $(x_1, y_1)$ and $(x_2, y_2)$ is $\sqrt{|x_1 - x_2|^2 + |y_1 - y_2|^2}$.

The answer can exceed $2^{64}$.