AT_agc076_e [AGC076E] Squared Norm Maximization

$ N $ 個の整数組 $ (A_1,B_1),(A_2,B_2),\cdots,(A_N,B_N) $ が与えられます． $ \{1,2,\cdots,N\} $ の部分集合 $ s $ に対し，その**スコア**を以下のように定義します． - $ (\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) $ スコアとしてありうる最大値を求めてください． $ 1 $ つの入力につき， $ T $ ケースを解いてください．

入力は以下の形式で標準入力から与えられる． > $ T $ $ case_1 $ $ case_2 $ $ \vdots $ $ case_T $ 各テストケースは以下の形式で与えられる． > $ N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_N $ $ B_N $

$ T $ 行出力せよ． $ i $ 行目には $ i $ ケース目に対する答えを出力せよ．

### Sample Explanation 1 $ 1 $ つ目のケースでは， $ s=\{\} $ とするとスコアが $ 0 $ になり，これが最大です． $ 2 $ つ目のケースでは， $ s=\{1,2,3,4\} $ とするとスコアが $ 4 $ になり，これが最大です． ### 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 $ - $ T $ ケースにわたる $ N $ の総和は $ 250000 $ 以下 - 入力はすべて整数