Problem K. Transport Construction

There are $n$ cities in Byteland, labeled by $1$ to $n$. The $i$-th city is located at $(x_i,y_i)$.
The Transport Construction Authority of Byteland is planning to open several bidirectional flights. Opening flight between the $i$-th city and the $j$-th city will cost $x_i\times x_j+y_i\times y_j$ dollars.
The Transport Construction Authority is now searching for the cheapest way to connect all of $n$ cities, so that every pair of different cities are connected by these flights directly or indirectly. Please write a program to find the cheapest way.

The first line of the input contains an integer $T(1\leq T\leq2000)$, denoting the number of test cases.
In each test case, there is an integer $n(2\leq n\leq 100000)$ in the first line, denoting the number of cities in Byteland.
For the next $n$ lines, each line contains $2$ integers $x_i,y_i(1\leq x_i,y_i\leq 10^6)$, denoting the coordinate of the $i$-th city. Note that different cities may have the same coordinate because they are too close to each other.
It is guaranteed that $\sum n\leq 10^6$.

For each test case, print a single line containing an integer, denoting the minimum total cost.

1
3
2 4
3 1
5 2

27

2018 Multi-University Training Contest 3