AT_agc076_e [AGC076E] Squared Norm Maximization

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.

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 $ T $ lines. The $ i $ -th line should contain the answer for the $ i $ -th case.

### Sample Explanation 1 In the first case, if $ s=\{\} $ , the score is $ 0 $ , which is the maximum. In the second case, if $ s=\{1,2,3,4\} $ , the score is $ 4 $ , which is the maximum. ### 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.