Pomekon Tournament
By Gabriel Duarte, UNIFESO 
Brazil
By Gabriel Duarte, UNIFESO Brazil
It will be held in your city a great tournament Pomekon where all the great Masters will play battles. The organizer of the event did not count with a lot of registrations, so the team modified a bit the tournament rules.
Instead of each Master Pomekon play alone the battles, doubles will be formed, the selection of pairs will be made by the organizing team, because as everyone knows the Pomekons Masters are solitary in their journeys, so no participant knows the other.
Participants of the tournament like the new rule, but were worried of not knowing your partner and end up not getting a good performance in the competition, so it was decided that the double would be formed by people who live as close as possible.
Your task in this problem is to form pairs so that the sum of the distances between the homes of each pair is the lowest possible. In other words, are X1 the distance between team members 1 and X2 the distance between team members 2, you should minimize the value of X1 + X2.
The entrance is composed of several instances. The first line of input contains an integer T indicating the number of instances.
Each instance begins with an even integer N (1 < N ≤ 16), which represents the amount of Master attached Pomekons. In the next N lines will have two integers Xi, Yi (0 ≤ Xi, Yi ≤ 1000), describing the coordinate of the participant's i home.
For each instance print the sum of the distances of the houses of all doubles, with two decimal places.
| Input Samples | Output Samples |
|
2 |
1.41 |