Chaos is spreading through the Milky Way Galaxy and dark forces are taking over.
Somewhere in the galaxy there exists the ancient interplanetary empire of Nara. The citizens of Nara are of a peaceful nature - avoiding war, preferring self-defense. But the darkness is destroying every civilization it encounters.
Fortunately, the smart engineers of Nara have managed to build laser-shield defence systems with the aim of protecting all the planets in the empire. How these systems work is that a laser shield is beamed from one planet to another. Once in place, the shield will form an impenetrable line of defence against the attackers. Any other planet falling on the path of a shield will also be protected. Equipment has to be set up on both the planet which is beaming the laser and the planet receiving it. Thus, all planets which come in the line of defence must be visited at least once. And this must be done swiftly, for the darkness is nearing.
Sadly, the engineers were just nerds who used to play around in their labs. They had neither any sense of distances in the Empire nor the courage to go to travel to faraway planets to set up the defence.
Gwil, who used to be a travelling salesman, knows the way around the Empire the best. He is assigned the task of setting up the defence system as fast as possible. He has to set up the shield equipment in a way that all planets of the empire are protected. He can start on any planet. He also has to minimize the distance that he needs to travel (so that he can be done quickly).
Gwil is pretty awesome and doesn’t really need your help, but asks for it anyway so that you can feel good about yourself. Write a program which takes the specified input and computes the minimum distance required to be covered.

Note:

1. Once equipment has been set up in a planet, it has the ability to both beam exactly one and receive exactly one laser shield. The equipment also protects the planet it is kept on.

2. Gwil obviously travels from planet to planet in a straight line. He will skip any other planet on that straight line as it will be protected automatically.

3. Assume the universe to be two dimensional.
   Input:

The first line will contain an integer T, the number of test cases.

T test cases follow, each described in the following manner.
The first line of each test case will contain an integer N, the number of planets in the empire.

The next N lines will contain two integers X[i] and Y[i] denoting the X and Y coordinates of the ith planet in the system.
Output:

For each test case, a single line containing the minimum distance exactly up to 2 digits after the decimal point. Use the double data type for all internal calculations.
Constraints:

1 ≤ T ≤ 10

1 ≤ N ≤ 10000

-10^4 ≤ X[i], Y[i] ≤ 10^4

SAMPLE INPUT
1
6
0 0
0 2
2 0
1 1
2 2
0 1

SAMPLE OUTPUT
6.00

Explanation

Gwil can start by setting up equipment at (0,0). Next he can visit (0,2) and set up. After that he can visit (2,2). And then finally, he visits (2,0) and sets up the equipment. Now, the shield is beamed from (0,0)->(0,2)->(2,2)->(2,0)->(0,0) and all 6 planets are protected.
Total distance covered = 6.00.

见题面

见题面