Description

给定一个有 $n$ 个顶点的凸多边形 $P$，您需要选择 $P$ 的两个顶点，并用一条同时穿过这两个顶点的直线，将 $P$ 分成两个面积均为正数的小多边形 $Q$ 和 $R$。

记 $d(Q)$ 表示多边形 $Q$ 的直径，$d(R)$ 表示多边形 $R$ 的直径，求 $(d(Q))^2 + (d(R))^2$ 的最小值。

请回忆：一个多边形的直径，指的是该多边形内部或边界上任意两点之间的距离的最大值。

Input Format

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据：

第一行输入一个整数 $n$（$4 \le n \le 5 \times 10^3$）表示凸多边形 $P$ 的顶点数量。

对于接下来 $n$ 行，第 $i$ 行输入两个整数 $x_i$ 和 $y_i$（$0 \le x_i, y_i \le 10^9$），表示凸多边形 $P$ 的第 $i$ 个顶点。顶点按逆时针顺序给出。保证该凸多边形面积为正，且没有顶点会重合。可能存在三个顶点位于同一条直线上的情况。

保证所有数据 $n$ 之和不超过 $5 \times 10^3$。

Output Format

每组数据输出一行一个整数表示答案。

【样例解释】

第一组样例数据如下图所示。小多边形的直径用红色虚线标出。事实上，顶点 $(1, 0)$ 和 $(1, 1)$ 是这一组数据中唯一能选择的一对顶点。您不能选择顶点 $(0, 0)$ 和 $(2, 0)$，或顶点 $(0, 0)$ 和 $(1, 1)$，因为它们无法将 $P$ 分成两个面积均为正数的小多边形。

第二组样例数据如下图所示。小多边形的直径用红色虚线标出。

2
4
1 0
2 0
1 1
0 0
6
10 4
9 7
5 7
4 5
6 4
9 3

4
44