Description

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

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

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

Input

有多组测试数据。第一行输入一个整数 \(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

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

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

Hint

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

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