#215780. [JAG 2023 Summer Camp #3] Convex Polygon MST

There is a convex polygon with vertices on a plane. Let be the set of vertices of this convex polygon. After removing all the edges of the convex polygon, you will create a tree with vertices by repeating the following operation times:

• Select two distinct vertices . Add an edge between vertices and . If we denote the Euclidean distance between vertices and as , you gain a score of points.

Find the maximum possible total score obtained by operations.

The input file contains multiple test cases. The first line contains an integer representing the number of test cases. Following that, test cases are given. Each test case is given in the following format:

Here, is an integer representing the number of vertices, where . The sum of all values in a single input file is guaranteed to be less than or equal to .

and represent the coordinates of the -th vertex, where each coordinate is an integer between to . The vertices are given in counterclockwise order when viewed from the centroid of the convex polygon. Three different vertices of the convex polygon do not lie on a single line.

Output the maximum possible total score obtained by operations.

样例输入 1

2
4
0 0
1 0
1 1
0 1
6
986288255 165031740
-353860917 -935298054
-173584601 -984818960
141060317 -990001002
341839727 -939758266
662792114 -748803453

样例输出 1

5
10426936519662708146

• The Euclidean distance between coordinates and is calculated as .
• Note that the answer can exceed .