As everyone else, you're a massive Lord of the Rings fan. One of your favourite pastimes is to take a printout of the map of Middle-Earth and mark all the major places. Then you connect them in some kind of pattern. You have a slightly skewed definition of fun.

Anyway, today's pattern is to minimize the amount of ink you need to connect all the places. You connect places by drawing a straight line between them, and you allow yourself to do so between arbitrary pairs of places. In the end, you want to have drawn lines such that there is a connection between any pair of places.


The input begins with a single positive integer on a line by itself indicating the number of test cases, followed by a blank line.

The first line of each test case contains \(0 < n \leq 100\), giving the number of places you have marked on your map. For each freckle, a line follows that contains two real numbers indicating the x and y coordinate of the freckle.

There is a blank line between each two consecutive test cases.


For each test case, your program must print a single real number to two decimal places: the minimum total length of ink lines that can connect all the freckles. The output of each two consecutive cases must be separated by a blank line.

Sample Input


1.0 1.0
2.0 2.0
2.0 4.0

Sample Output


This is challenge 10034 of the ACM International Collegiate Programming Contest. Test input is provided by uDebug.

Upload Solution

Please log in to submit your solution.


Difficulty (1 vote)
Average test runtime 3.83
Points (changes over time) 10
Tried by 7 users
Solved by 6 users

Global ranking

# Name Runtime Points worth
1 贝尔恩德 0.27 27
2 JB 0.31 24
3 Dark 2.21 3
4 Mac 2.40 3
5 Skøgland 4.46 2
6 Pascal 13.35 1