You have been given the job of forming the quiz teams for the next ‘MCA CPCI Quiz Championship’.

There are $2 ∗ N$ students interested to participate and you have to form $N$ teams, each team consisting of two members. Since the members have to practice together, all the students want their members house as near as possible. 

Let $x_1$ be the distance between the houses of group $1$, $x_2$ be the distance between the houses of group $2$ and so on. You have to make sure the summation $(x_1+x_2+x_3+. . .+x_n)$ is minimized.

There will be many cases in the input file. 

Each case starts with an integer $N\ (N ≤ 8)$. 

The next $2 ∗ N$ lines will given the information of the students. Each line starts with the students name, followed by the $x$ coordinate and then the $y$ coordinate. Both $x, y$ are integers in the range $0$ to $1,000$. Students name will consist of lowercase letters only and the length will be at most $20$. 

Input is terminated by a case where $N$ is equal to $0$.

For each case, output the case number followed by the summation of the distances, rounded to $2$ decimal places. Follow the sample for exact format