ankur-and-girlfriend-1

"Intelligence is a very result of hard work, behind every drop of intelligence there is a ocean of hard work" - Unknown

So our guy Ankur likes a girl G very much. But as we all know G likes only intelligent guys. 
So if Ankur has to impress her then he has to show his intelligence. But G too is an intelligent girl, so he came up with a task for Ankur.
The task is -
Ankur has to collect flowers for her and put them into baskets, but flowers are scattered all around,
 each flower has a position say (x,y). Each basket can hold only two flowers, but putting flowers into basket has a special cost. 
 If two flowers at positions (x1,y1) and (x2,y2) are being put into a basket then cost of putting them will be 
 the euclidean distance between them ( sqrt(square(x2-x1) + square((y2-y1))).

So there are 2*N flowers and N baskets. 
He has to put all the flowers into the baskets and give her the final total cost.
But this total cost would be minimum.
Hence He has to minimize Summation ( c1+c2+c3+...+cn) , where ci is the cost of putting two flowers into ith basket.
ci = sqrt(square(x2-x1) + square((y2-y1)) , if two flowers at coordinates (x1,y1) and (x2,y2) are being put into ith basket

Input

First line gives the number of testcases  1 ≤ T ≤ 100.
Each case starts with an integer N (1 ≤ N ≤ 8). The next 2*N lines will give
the coordinates of a flower. Each line starts with the x coordinate and then the y coordinate. Both x, y are integers in the range 0 to 1000. 

Output

For each case, output the minimum total cost, rounded to 2 decimal places. Follow the sample for exact format.

SAMPLE INPUT
3
1
9 9
10 10
2
0 0
1 0
4 1
5 1
5
10 10
20 10
5 5
1 1
120 3
6 6
50 60
3 24
6 9
0 0

SAMPLE OUTPUT
1.41
2.00
118.40

Explanation

For the first case we can just put both the flowers in the basket, so the cost will be sqrt((10-9)(10-9)+(10-9)(10-9))
For the second case we can put flower(0,0) and flower(1,0) in first basket, so c1 = sqrt((1-0)(1-0)+(0-0)(0-0)) and c2 = sqrt((5-4)(5-4)+(1-1)(1-1))
this (c1+c2) would be minimum.
but if we put let's say (0,0) and (4,1) in first and (1,0) and (5,1) in second, the (c1+c2) would not be minimum.

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: