선분 연결하기

사랑하는 아들 Arnie는 Connect Line Segments라는 퍼즐에 빠져 있다.

이 퍼즐에서는 2차원 평면 위에 여러 선분이 주어진다. 두 선분의 끝점을 잇는 새로운 선분을 몇 개든 추가할 수 있다. 목표는 주어진 모든 선분을 연결해 하나의 꺾은선을 만들되, 그 길이를 최소로 하는 것이다. 만들어진 꺾은선은 자기 자신과 교차해도 된다.

Arnie는 지금까지 많은 문제를 나름의 방식으로 풀어 왔지만, 자신의 답이 최선인지 궁금해한다. Arnie는 당신이 뛰어난 프로그래머라는 사실을 알고 있어, 자신의 답을 검증할 프로그램을 만들어 달라고 부탁했다.

사랑하는 Arnie의 부탁을 들어주자.

입력은 여러 테스트 케이스로 이루어진다.

각 테스트 케이스는 정수 n (2 ≤ n ≤ 14) 하나가 주어지는 줄로 시작한다. n은 처음에 주어지는 선분의 개수이다. 다음 n개 줄은 선분의 정보를 나타낸다. i번째 줄에는 실수 네 개 x**i,1, y**i,1, x**i,2, y**i,2가 주어진다 (-100 ≤ x**i,1, y**i,1, x**i,2, y**i,2 ≤ 100). (x**i,1, y**i,1)과 (x**i,2, y**i,2)는 i번째 선분의 두 끝점 좌표이다.

입력의 끝은 “0” 하나만 있는 줄로 나타난다.

각 테스트 케이스마다 케이스 번호와 최소 길이를 한 줄에 출력한다.

출력값은 소수점 아래 다섯 자리까지 출력해야 하며, 오차가 0.00001을 넘으면 안 된다.