Pokémon Go! X50305

José, primo de José e Maria e calouro do Curso de Ciência da Computação, ficou muito feliz ao descobrir que a UFMA é repleta de pokéstops.

Como é esperto, ele fez um mapa com as coordenadas de cada ponto e pediu sua ajuda para traçar o melhor caminho para percorrer todos os pokéstops.

Dado um mapa com uma sequência de pontos, você deve encontrar o menor caminho que José deve fazer para que, partindo de um pokéstop, consiga visitar todos os outros.

Input

A entrada começa com um número positivo que representa a quantidade de casos de teste.

Em seguida, temos o número $n$ que é a quantidade de pokéstops que José encontrou na UFMA, seguido de $n$ linhas, cada uma com dois números reais que representam as coordenadas $(x, y)$ de um ponto do mapa.

Output

Para cada caso de teste, imprima uma linha com o percurso total que José andou para visitar todos os pokéstops. A resposta deve ser um número real com duas casas decimais.