Jack Edmonds

Jack Edmonds is an American computer scientist. Programmers who train for algorithm contests know him as a co-inventor of the Edmonds-Karp algorithm, which solves the maximum flow problem in $O(|V||E|^2)$. His larger contribution may be the Cobham-Edmonds thesis, which defines polynomial time as the criterion for whether an algorithm is practical. Today we treat a problem in P (deterministic polynomial time) as efficiently solvable and a problem in NP (nondeterministic polynomial time) as efficiently verifiable. The P versus NP problem asks whether P equals NP. It is the largest open problem in computer science, and one of the seven Millennium Prize Problems. Most computer scientists believe that P $\ne$ NP, and nobody has proved it. Others have tried to prove P = NP by placing some NP-hard problem in P, and all of them failed.

The traveling salesperson problem is one example of an NP-hard problem. Given a list of destinations and the distance between every pair of destinations, find the shortest route that starts at the origin, visits every destination, and returns to the origin. This problem has no map. You get the coordinates of the destinations, and no road has been built yet.

The city mayor builds the roads for you. He is simple and lazy. One road connects two destinations $(x_i, y_i)$ and $(x_j, y_j)$ directly, using horizontal and vertical segments only, so its length is $|x_i - x_j| + |y_i - y_j|$. He will not build more than $n - 1$ roads. You decide which roads he builds.

You travel only on the roads that were built. You may walk the same road several times, and you may pass the same destination several times. Report the length of the shortest route that starts at the first destination, visits every destination, and returns to the first destination.

The first line contains the number of test cases $T$ ($1 \le T \le 20$).

The first line of each test case contains the number of destinations $n$ ($1 \le n \le 10\,000$). Each of the next $n$ lines contains two integers $x$ and $y$, the coordinates of one destination ($-1\,000 \le x, y \le 1\,000$). The destination given first is the origin. Two destinations may have the same coordinates.

For each test case, print on one line the length of the shortest route that visits every destination and returns to the origin.