問題文

2 次元平面上に相異なる N 個の点があり、それぞれ 1 から N までの番号が付けられています。点 i の座標は (x_i, y_i) です。

また、それぞれの点には色が付けられています。色の種類は N 個あり、それぞれ 1 から N までの番号が付けられています。点 i の色は c_i です。

あなたは、これらの点から色の相異なる 4 点を選び、任意の順でつないで 1 つの四角形を作ります。この四角形はちょうど 180 度の内角を持っていても構いませんが、連続しないどの 2 辺も共通部分を持ってはいけません。

そのように四角形を作ることができるかどうか判定し、できる場合はその四角形の面積としてあり得る最大値を S として 2S を出力してください。できない場合は 0 を出力してください。

T 個のテストケースが与えられるので、それぞれについて解いてください。

制約

• 入力はすべて整数
• 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)
• T 個のテストケースに渡る 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 番目のテストケースでは、点 1,2,3,6 をこの順でつないでできる四角形は条件を満たしており、その面積は 15/2 です。この四角形は条件を満たす四角形のうち面積が最大です。点 1,2,4,5 をこの順でつないでできる四角形の面積は 9 ですが、点 1,4 の色は同じなので、この四角形は条件を満たしていません。

2 番目のテストケースでは、条件を満たす四角形を作ることができますが、凸であるものを作ることはできません。

3 番目のテストケースでは、条件を満たす四角形を作ることはできません。

4 番目のテストケースのように、答えが非常に大きくなる場合があることに注意してください。