Squares

There are $n$ axis-parallel squares in the plane. Each square is given by the coordinates $(x, y)$ of its lower-left corner and the side length $w$; every side is parallel to the $x$-axis or the $y$-axis. The squares may have different sizes, may overlap, and may share corners.

From each square you choose exactly one point (any point inside the square, boundary included). For the chosen set of points, the diameter is defined as the maximum Euclidean distance between any pair of them. You want to choose one point from every square so that the diameter of the chosen points is as large as possible.

Let $D$ be that maximum possible diameter. Output $D^2$, the square of $D$, as an integer.

As in the figure above with six squares, the largest diameter is the distance between two corner points taken from two different squares. The value $D^2$ is always an integer.

The first line contains the number of test cases $T$. Each test case begins with a line containing the number of squares $n$ ($2 \le n \le 100{,}000$). Each of the next $n$ lines contains three integers $x$, $y$, and $w$, where $(x, y)$ is the lower-left corner of a square and $w$ is its side length ($0 \le x, y \le 10{,}000$ and $1 \le w \le 10{,}000$).

For each test case, print a single line containing $D^2$, the square of the largest diameter $D$ obtainable by choosing one point from each square.