You are given $N$ distinct points on the 2D plane, numbered $1$ through $N$. The coordinates of point $i$ are $(x_i, y_i)$.
Each point has a color. There are $N$ colors in total, numbered $1$ through $N$, and point $i$ has color $c_i$.
Your task is to select four points with pairwise distinct colors, connect them in any order, and form a quadrilateral. The quadrilateral may have an interior angle of exactly $180^\circ$, but no pair of non-adjacent edges may intersect.
Determine whether such a quadrilateral can be formed. If it can, let $S$ be the maximum possible area over all valid quadrilaterals, and output $2S$ as an integer. If it cannot be formed, output $0$.
There are $T$ independent test cases.
Input
The input is given in the following format:
T case1 case2 : caseT
Here, each $\text{case}_i$ is given in the following form:
N x1 y1 c1 x2 y2 c2 : xN yN cN
- All input values are integers.
- $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$
- If $i \neq j$, then $(x_i, y_i) \neq (x_j, y_j)$.
- The total sum of $N$ over all test cases does not exceed $10^5$.
Output
For each test case, output the answer on its own line.
Examples
Sample Input 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
Sample Output 1
15 17 0 20000000000000000
Note
In the first example, connecting points $1, 2, 3, 6$ in this order forms a valid quadrilateral with area $15/2$, which is the maximum among all valid choices. The quadrilateral formed by points $1, 2, 4, 5$ has area $9$, but points $1$ and $4$ share the same color, so it is invalid.
In the second example, a valid quadrilateral exists, but no convex quadrilateral satisfies the requirements.
In the third example, no valid quadrilateral can be formed.
As shown in the fourth example, the answer can be very large.