D. Tuples Fusion
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$n$$$ tuples $$$(a_i,b_i)$$$. In the beginning, your score is $$$0$$$.

You can do the following operation any number of times in any order:

  1. Choose an index $$$i$$$ ($$$1\le i\le n$$$), add $$$(a_i+b_i)^2$$$ to your score, then set $$$a_i=b_i=0$$$;
  2. Choose two distinct indexes $$$i,j$$$ ($$$1\le i,j\le n$$$), add $$$a_j^2$$$ to your score, add $$$b_j$$$ to $$$b_i$$$, then set $$$a_j=b_j=0$$$.
  3. Choose two distinct indexes $$$i,j$$$ ($$$1\le i,j\le n$$$), add $$$b_j^2$$$ to your score, add $$$a_j$$$ to $$$a_i$$$, then set $$$a_j=b_j=0$$$.
Find the maximum score you can get.
Input

The first line contains a single integer $$$t$$$ ($$$1 \le t\le 10^4$$$), the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n\le 2 \cdot 10^5$$$).

The next $$$n$$$ lines of each test case contain two integers $$$a_i,b_i$$$ ($$$1\le a_i,b_i\le 10^9$$$).

It is guaranteed that the sum of $$$n$$$ for all tests does not exceed $$$2 \cdot 10^5$$$, and the answer for each test case won't exceed $$$9.2 \cdot 10^{18}$$$.

Output

For each test case, output the maximum score you can get.

Example
Input
3
2
1 1
1000000000 1000000000
3
1 3
2 6
3 9
6
85 65
35 59
2 65
789 21
12 32
9 8
Output
4000000004000000002
446
1220694
Note

In the first case, we can do the following operations:

  • Choose $$$i=2$$$ and $$$j=1$$$, add $$$b_j^2$$$ to your score, add $$$a_j$$$ to $$$a_i$$$, then set $$$a_i=b_i=0$$$. After that, $$$(a_1,b_1)=(0,0)$$$, $$$(a_2,b_2)=(1000000001,1000000000)$$$ and you score is $$$1$$$;
  • Choose $$$i=2$$$ add $$$(a_i+b_i)^2$$$ to your score, then set $$$a_i=b_i=0$$$. After that, $$$(a_1,b_1)=(0,0)$$$, $$$(a_2,b_2)=(0,0)$$$ and you score is $$$4000000004000000002$$$.

It can be proven that $$$4000000004000000002$$$ is the maximum of your score.

You can also do the following operations to get the maximum of your score:

  • Choose $$$i=2$$$ and $$$j=1$$$, add $$$a_j^2$$$ to your score, add $$$b_j$$$ to $$$b_i$$$, then set $$$a_i=b_i=0$$$. After that, $$$(a_1,b_1)=(0,0)$$$, $$$(a_2,b_2)=(1000000000,1000000001)$$$ and you score is $$$1$$$;
  • Choose $$$i=2$$$, add $$$(a_i+b_i)^2$$$ to your score, then set $$$a_i=b_i=0$$$. After that, $$$(a_1,b_1)=(0,0)$$$, $$$(a_2,b_2)=(0,0)$$$ and you score is $$$4000000004000000002$$$.