Your dear son Arnie is addicted to a puzzle named Connect Line Segments.

In this puzzle, you are given several line segments placed on a two-dimensional area. You are allowed to add some new line segments each connecting the end points of two existing line segments. The objective is to form a single polyline, by connecting all given line segments, as short as possible. The resulting polyline is allowed to intersect itself.

<image>

Arnie has solved many instances by his own way, but he is wondering if his solutions are the best one. He knows you are a good programmer, so he asked you to write a computer program with which he can verify his solutions.

Please respond to your dear Arnie’s request.



Input

The input consists of multiple test cases.

Each test case begins with a line containing a single integer n (2 ≤ n ≤ 14), which is the number of the initial line segments. The following n lines are the description of the line segments. The i-th line consists of four real numbers: xi,1, yi,1, xi,2, and yi,2 (-100 ≤ xi,1, yi,1, xi,2, yi,2 ≤ 100). (xi,1, yi,1) and (xi,2, yi,2) are the coordinates of the end points of the i-th line segment.

The end of the input is indicated by a line with single “0”.

Output

For each test case, output the case number followed by the minimum length in a line.

The output value should be printed with five digits after the decimal point, and should not contain an error greater than 0.00001.

Example

Input

4
0 1 0 9
10 1 10 9
1 0 9 0
1 10 9 10
2
1.2 3.4 5.6 7.8
5.6 3.4 1.2 7.8
0


Output

Case 1: 36.24264
Case 2: 16.84508
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <complex>
#include <vector>
#include <cmath>

using namespace std;

#define MAXN (17)
#define INF  (1<<29)
#define X    real()
#define Y    imag()

typedef complex<double> P;

template<class T>
inline T Sq(T x) { return x*x; }

inline double getDist(P, P);
struct Segment {
  P s, t;
  double d;
  Segment() {}
  Segment(P s, P t) : s(s), t(t) { d = getDist(s, t); }
};

inline double getDist(P a, P b) { return sqrt(Sq(a.X-b.X)+Sq(a.Y-b.Y)); }
inline double getDist(Segment sg) { return sqrt(Sq(sg.s.X-sg.t.X)+Sq(sg.s.Y-sg.t.Y)); }

int n;
double dist[MAXN][2][MAXN][2]; // seg s: 0, t: 1
double dp[1<<MAXN][MAXN][2];
Segment seg[MAXN];

int main() {
  
  int tcase = 1;
  double x1, y1, x2, y2;
  double allseglen;
  
  while(cin >> n, n) {
    
    allseglen = 0.0;
    
    for(int i=0; i<n; i++) {
      cin >> x1 >> y1 >> x2 >> y2;
      seg[i] = Segment(P(x1, y1), P(x2, y2));
      allseglen += seg[i].d;
    }
    
    for(int i=0; i<n; i++) {
      for(int j=0; j<n; j++) {
	
	if(i == j) {
	  for(int ii=0; ii<2; ii++) {
	    for(int jj=0; jj<2; jj++) {
	      if(ii == jj) { dist[i][ii][j][jj] = 0; }
	      else { dist[i][ii][j][jj] = seg[i].d; }
	    }
	  }
	  
	  continue;
	}
	
	dist[i][0][j][0] = getDist(seg[i].s, seg[j].s);
	dist[i][0][j][1] = getDist(seg[i].s, seg[j].t);
	dist[i][1][j][0] = getDist(seg[i].t, seg[j].s);
	dist[i][1][j][1] = getDist(seg[i].t, seg[j].t);
	
      }
    }
        
    for(int i=0; i<(1<<n); i++)
      for(int j=0; j<n; j++)
	for(int k=0; k<2; k++)
	  dp[i][j][k] = INF;
      
    for(int i=0; i<n; i++)
      for(int j=0; j<2; j++)
	dp[1<<i][i][j] = 0;
    
    for(int S=0; S<(1<<n); S++){
      for(int u=0; u<n; u++){
	if( !( (S>>u) & 1 ) ) continue;
	for(int i=0; i<2; i++){
	  if(dp[S][u][i] == INF) continue;
	  for(int v=0; v<n; v++){
	    if( (S>>v) & 1 ) continue;
	    if(u == v) continue;
	    for(int j=0; j<2; j++){
	      int T = S | (1<<v);
	      dp[T][v][j] = min(dp[T][v][j], dp[S][u][i] + dist[u][(i+1)&1][v][j]);
	    }
	  }
	}
      }
    }
    
    double ans = INF;
    for(int i=0; i<n; i++)
      for(int j=0; j<2; j++)
	ans = min(ans, dp[(1<<n)-1][i][j]);
    
    printf("Case %d: %f\n", tcase++, ans + allseglen);
  }
  
  return 0;
}