볼록 다각형 MST

평면 위에 꼭짓점이 $n$개인 볼록 다각형이 있다. 꼭짓점의 집합을 $V$라고 하자. 볼록 다각형의 변을 모두 제거한 뒤, 다음 연산을 $n-1$번 반복하여 꼭짓점이 $n$개인 트리를 만든다:

• 서로 다른 두 꼭짓점 $x, y \in V$를 고른다. $x$와 $y$ 사이에 간선을 추가한다. 두 점 사이의 유클리드 거리를 $d(x,y)$라고 하면, $(d(x,y))^2$점을 얻는다.

$n-1$번의 연산으로 얻을 수 있는 점수 합의 최댓값을 구하시오.

입력 파일에는 여러 개의 테스트 케이스가 들어 있다. 첫 줄에는 테스트 케이스의 개수 $t$가 주어진다. 이어서 $t$개의 테스트 케이스가 주어지며, 각 테스트 케이스는 다음 형식으로 주어진다.

$n$

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

$n$은 꼭짓점의 개수이며 $3 \le n \le 120\,000$이다. 한 입력 파일에 있는 모든 $n$의 합은 $120\,000$ 이하이다. $x_i$와 $y_i$는 $i$번째 꼭짓점의 좌표이며, 각 좌표는 $-10^9$ 이상 $10^9$ 이하의 정수이다. 꼭짓점은 볼록 다각형의 무게중심에서 볼 때 반시계 방향으로 주어진다. 볼록 다각형의 서로 다른 세 꼭짓점은 한 직선 위에 있지 않다.

점수 합의 최댓값을 출력한다.

두 점 $(x_1, y_1)$과 $(x_2, y_2)$ 사이의 유클리드 거리는 $\sqrt{|x_1 - x_2|^2 + |y_1 - y_2|^2}$으로 계산한다.

답은 $2^{64}$를 넘을 수 있다.