Problem Statement

You are a magic warrior on a two-dimensional plane, initially located at point $(0, 0)$.

$N$ events will now occur. In the $i$-th event ($1 \leq i \leq N$), one monster appears at point $(X_i, Y_i)$, and you choose whether to defeat this monster with a sword or with magic.

• If you choose to defeat the monster with a sword, you move to point $(X_i, Y_i)$. This incurs a cost equal to the square of the Euclidean distance between the point where you were located before moving and point $(X_i, Y_i)$.
• If you choose to defeat the monster with magic, a cost of $Z_i$ is incurred. In this case, you do not move.

Find the minimum total cost eventually required.

What is Euclidean distance? The Euclidean distance between point $(a, b)$ and point $(c, d)$ is defined as $\sqrt{(a - c)^2 + (b - d)^2}$.

Solve $T$ test cases per input file.

Constraints

• $1 \leq T \leq 10$
• $1 \leq N \leq 250\,000$
• $0 \leq X_i < 500$ ($1 \leq i \leq N$)
• $0 \leq Y_i < 500$ ($1 \leq i \leq N$)
• $1 \leq Z_i \leq 10^9$ ($1 \leq i \leq N$)
• The sum of $N$ over the $T$ test cases is at most $250\,000$.
• All input values are integers.

Input

The input is given from Standard Input in the following format. Here, $\mathrm{case}_i$ ($1 \leq i \leq T$) denotes the $i$-th test case.

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is given in the following format:

N
X_1 Y_1 Z_1
X_2 Y_2 Z_2
\vdots
X_N Y_N Z_N

Output

Output $T$ lines. The $i$-th line ($1 \leq i \leq T$) should contain the answer for $\mathrm{case}_i$.