{"raw_statement":[{"iden":"problem statement","content":"You are given $N$ pairs of integers $(A_1,B_1),(A_2,B_2),\\cdots,(A_N,B_N)$.\nFor a subset $s$ of ${1,2,\\cdots,N}$, we define its **score** as follows:\n\n*   $(\\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)$\n\nFind the maximum possible value of the score.\nSolve $T$ cases for one input."},{"iden":"constraints","content":"*   $1 \\leq T \\leq 250000$\n*   $1 \\leq N \\leq 250000$\n*   $\\sum_{1 \\leq i \\leq N} |A_i| \\leq 10^9$\n*   $\\sum_{1 \\leq i \\leq N} |B_i| \\leq 10^9$\n*   The sum of $N$ over the $T$ cases is at most $250000$.\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$T$\n$case_1$\n$case_2$\n$\\vdots$\n$case_T$\n\nEach test case is given in the following format:\n\n$N$\n$A_1$ $B_1$\n$A_2$ $B_2$\n$\\vdots$\n$A_N$ $B_N$"},{"iden":"sample input 1","content":"4\n4\n1 0\n0 1\n-1 0\n0 -1\n4\n1 0\n1 0\n1 0\n1 0\n6\n1 -9\n-7 -2\n0 -10\n10 1\n2 -8\n1 -8\n10\n19271058 -140039457\n-3441379 -134156148\n227767903 -70474702\n-837477 -74699717\n153584327 80404336\n115741008 -22141349\n-190028077 -21940357\n76149725 17176032\n159846847 -296045185\n-53332199 142922717"},{"iden":"sample output 1","content":"0\n4\n296\n178262497119089558\n\nIn the first case, if $s={}$, the score is $0$, which is the maximum.\nIn the second case, if $s={1,2,3,4}$, the score is $4$, which is the maximum."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}