平面上有一个具有 $n$ 个顶点的凸多边形。考虑一个无向图 $(V, E)$，其中 $V$ 是该凸多边形的顶点集合，$E$ 初始为空。重复以下操作 $n-1$ 次，使得最终图成为一棵树：

• 从 $V$ 中选择两个不同的顶点 $u$ 和 $v$。
• 在顶点 $u$ 和 $v$ 之间添加一条边到 $E$ 中。
• 如果我们用 $d(u, v)$ 表示顶点 $u$ 和 $v$ 之间的欧几里得距离，你将获得 $(d(u, v))^2$ 点分数。

求在 $n-1$ 次操作后能获得的最大总分数。

输入格式

输入的第一行包含一个整数 $t$：测试用例的数量。接下来是各测试用例。 每个测试用例的第一行包含一个整数 $n$：多边形的顶点数（$3 \le n \le 120\,000$）。 接下来 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$：多边形第 $i$ 个顶点的坐标（$-10^9 \le x_i, y_i \le 10^9$）。顶点按逆时针顺序给出。保证多边形是凸的。没有三个顶点在同一直线上。 单个输入中所有 $n$ 的总和不超过 $120\,000$。

输出格式

对于每个测试用例，输出一行，包含一个整数：在构成树的 $n-1$ 次操作后能获得的最大总分数。

样例

输入 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

说明

注意答案可能超过 $2^{64}$。