Problem Statement

You are given $N$ pairs of integers $(A_1,B_1),(A_2,B_2),\cdots,(A_N,B_N)$.

For a subset $s$ of $\{1,2,\cdots,N\}$, we define its score as follows:

• $(\sum_{i \in s} A_i)^2 + (\sum_{i \in s} B_i)^2 - 3 \sum_{i \in s} (A_i^2+B_i^2)$

Find the maximum possible value of the score.

Solve $T$ cases for one input.

Constraints

• $1 \leq T \leq 250000$
• $1 \leq N \leq 250000$
• $\sum_{1 \leq i \leq N} |A_i| \leq 10^9$
• $\sum_{1 \leq i \leq N} |B_i| \leq 10^9$
• The sum of $N$ over the $T$ cases is at most $250000$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

T
case_1
case_2
\vdots
case_T

Each test case is given in the following format:

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Output $T$ lines. The $i$-th line should contain the answer for the $i$-th case.