在二维平面上给定 $N$ 个不同的点，编号为 $1$ 到 $N$。点 $i$ 的坐标为 $(x_i, y_i)$。

每个点都有一种颜色。一共有 $N$ 种颜色，编号为 $1$ 到 $N$，点 $i$ 的颜色为 $c_i$。

你的任务是选择四个颜色两两不同的点，按某种顺序连接它们以组成一个四边形。该四边形可以包含恰好为 $180^\circ$ 的内角，但任意两条不相邻的边不能相交。

确定是否可以组成这样的四边形。如果可以，设 $S$ 为所有合法四边形的最大可能面积，并以整数形式输出 $2S$。如果无法组成，输出 $0$。

共有 $T$ 组独立的测试数据。

输入格式

输入按以下格式给出：

T
case1
case2
:
caseT

其中，每个 $\text{case}_i$ 的格式如下：

N
x1 y1 c1
x2 y2 c2
:
xN yN cN

数据范围

• 所有输入值均为整数。
• $1 \le T \le 10^4$
• $4 \le N \le 10^5$
• $|x_i|, |y_i| \le 10^8$
• $1 \le c_i \le N$
• 若 $i \neq j$，则 $(x_i, y_i) \neq (x_j, y_j)$
• 所有测试数据的 $N$ 之和不超过 $10^5$

输出格式

对于每组测试数据，单独输出一行表示答案。

样例

输入样例 1

4
6
2 4 1
5 4 2
6 2 3
5 1 1
2 1 2
1 3 4
4
1 1 1
3 5 2
7 2 3
4 3 4
5
0 0 1
0 1 2
1 0 2
0 2 3
2 0 3
4
0 0 1
0 100000000 2
100000000 0 3
100000000 100000000 4

输出样例 1

15
17
0
20000000000000000

说明

在第一个样例中，按顺序连接点 $1, 2, 3, 6$ 可以组成一个合法的四边形，其面积为 $15/2$，这是所有合法选择中的最大值。由点 $1, 2, 4, 5$ 组成的四边形面积为 $9$，但点 $1$ 和点 $4$ 颜色相同，因此不合法。

在第二个样例中，存在合法的四边形，但没有凸四边形满足要求。

在第三个样例中，无法组成任何合法的四边形。

如第四个样例所示，答案可能会非常大。