K. 2.. 3.. 4.. Colorful! Colorful! Colorful!
time limit per test
4.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given $$$n$$$ distinct points $$$(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$$$.

Each point $$$i$$$ has a color $$$c_i$$$.

Find the $$$\textbf{squared}$$$ Euclidean distance between the farthest pair of points that are not from the same color.

Note: The Euclidean distance between two points $$$(a_1, b_1)$$$ and $$$(a_2, b_2)$$$ is defined as follows: $$$\sqrt{(a_1 - a_2)^2 + (b_1 - b_2)^2}$$$.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 5 \cdot 10^5$$$) — the number of testcases.

The first line of each testcase contains a single integer $$$n$$$ ($$$2 \le n \le 10^6$$$) — the number of points.

Each of the next $$$n$$$ lines of each testcase consists of three space-separated integers, $$$x_i$$$, $$$y_i$$$, and $$$c_i$$$ ($$$|x_i|, |y_i| \le 10^9$$$ and $$$1 \le c_i \le n$$$).

It is guaranteed that if $$$i \ne j$$$ then $$$(x_i, y_i, c_i) \ne (x_j, y_j, c_j)$$$.

It is also guaranteed that there will be at least two different colors among the colors of the $$$n$$$ points.

It is also guaranteed that the sum of $$$n$$$ over all testcases will not exceed $$$10^6$$$.

Output

For each testcase, output a single line containing a single integer, the squared Euclidean distance between the farthest pair of points that are from different colors.

Examples
Input
2
4
0 0 1
0 1 2
1 0 2
2 2 1
3
0 0 1
1 1 2
2 2 3
Output
5
8
Input
1
2
-1 -1 1
-3 -4 2
Output
13