Problem: Mr. KM, the mayor of KM city, decided to build a new elementary school. The site for the school has an awkward polygonal shape, which caused several problems. The most serious problem was that there was not enough space for a short distance racetrack. Your task is to help Mr. KM to calculate the maximum possible length for the racetrack that can be built in the site. The track can be considered as a straight line segment whose width can be ignored. The boundary of the site has a simple polygonal shape without self-intersection, and the track can touch the boundary. Note that the boundary might not be convex.



Input

The input consists of multiple test cases, followed by a line containing "0". Each test case has the following format. The first line contains an integer N (3 \leq N \leq 100). Each of the following N lines contains two integers x_i and y_i (-1,000 \leq x_i, y_i \leq 1,000), which describe the coordinates of a vertex of the polygonal border of the site, in counterclockwise order.

Output

For each test case, print its case number and the maximum possible length of the track in a line. The answer should be given as a floating point number with an absolute error of at most 10^{-6}.

Example

Input

4
0 0
10 0
10 10
0 10
3
0 0
1 0
0 1
0


Output

Case 1: 14.142135624
Case 2: 1.41421356

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
#define inf 1<<29
#define linf 1e16
#define eps (1e-6)
#define mod 1000000007
#define pi acos(-1)
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define pd(a) printf("%.10f\n",(double)(a))
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(a)-1;(b)<=i;i--)
#define equals(a,b) (fabs((a)-(b))<eps)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,double> pid;
typedef pair<double,int> pdi;
typedef vector<int> vi;
typedef vector<pii> vpi;
const int dx[8]={1,0,-1,0,1,1,-1,-1};
const int dy[8]={0,1,0,-1,1,-1,1,-1};

class Point{
public:
  double x,y;
  Point(double x=0,double y=0):x(x),y(y){}

  Point operator+(Point p){ return Point(x+p.x,y+p.y);}
  Point operator-(Point p){ return Point(x-p.x,y-p.y);}
  Point operator*(double k){ return Point(x*k,y*k);}
  Point operator/(double k){ return Point(x/k,y/k);}
  bool operator<(Point p)const{ 
    return (x!=p.x ? x-p.x<-eps : y-p.y<-eps);}
  bool operator==(Point p)const{ 
    return fabs(x-p.x)<eps && fabs(y-p.y)<eps;}

  double abs(){ return sqrt(norm());}
  double norm(){ return (x*x+y*y);}
};
typedef Point Vector;
typedef vector<Point> Polygon;

class Segment{
public:
  Point p1,p2;
  Segment(Point p1=Point(),Point p2=Point()):p1(p1),p2(p2){}
};
typedef Segment Line;

double norm(Vector a){ return (a.x*a.x+a.y*a.y);}
double abs(Vector a){ return sqrt(norm(a));}
double dot(Vector a,Vector b){ return (a.x*b.x+a.y*b.y);}
double cross(Vector a,Vector b){ return (a.x*b.y-a.y*b.x);}

bool isParallel(Vector a,Vector b){
  return equals(cross(a,b),0.0);
}

bool isParallel(Segment s,Segment t){
  return equals(cross(s.p1-s.p2,t.p1-t.p2),0.0);
}

Point getCrossPointLL(Line a,Line b){
  double A=cross(a.p2-a.p1,b.p2-b.p1);
  double B=cross(a.p2-a.p1,a.p2-b.p1);
  if(abs(A)<eps || abs(B)<eps)return b.p1;
  return b.p1+(b.p2-b.p1)*(B/A);
}

int ccw(Point p0,Point p1,Point p2){
  Vector a=p1-p0;
  Vector b=p2-p0;
  if(cross(a,b)>eps)return 1;
  if(cross(a,b)<-eps)return -1;
  if(dot(a,b)<-eps)return 2;
  if(a.norm()<b.norm())return -2;
  return 0;
}

bool intersect(Point p1,Point p2,Point p3,Point p4){
  return (ccw(p1,p2,p3)*ccw(p1,p2,p4)<=0 &&
          ccw(p3,p4,p1)*ccw(p3,p4,p2)<=0);
}

bool intersect(Segment s1,Segment s2){
  return intersect(s1.p1,s1.p2,s2.p1,s2.p2);
}

bool intersectLS(Line l,Segment s){
  if(cross(l.p2-l.p1,s.p1-l.p1)*
     cross(l.p2-l.p1,s.p2-l.p1)<eps)return true;
  return false;
}
 
int contains(Polygon g,Point p){
  int n=g.size();
  bool x=false;
  for(int i=0;i<n;i++){
    Vector a=g[i]-p,b=g[(i+1)%n]-p;
    if(abs(cross(a,b))<eps && dot(a,b)<eps)return 1;
    if(a.y>b.y)swap(a,b);
    if(a.y<eps && eps<b.y && cross(a,b)>eps)x=!x;
  }
  if(x)return 2;
  return 0;
}

Polygon convex_hull(Polygon s){
  Polygon g;
  int n=s.size();
  if(n<3)return s;

  sort(s.begin(),s.end());

  for(int i=0;i<n;i++){
    for(int n=g.size();n>=2&&ccw(g[n-2],g[n-1],s[i])==1;n--){
      g.pop_back();
    }
    g.push_back(s[i]);
  }
  for(int i=n-2;i>=0;i--){
    for(int n=g.size();n>=2&&ccw(g[n-2],g[n-1],s[i])==1;n--){
      g.pop_back();
    }
    g.push_back(s[i]);
  }
  reverse(g.begin(),g.end());
  g.pop_back();
  return g;
}

vector<Line> getTangent(Polygon a,Polygon b){
  vector<Line> res;
  int n=a.size(),m=b.size();

  FOR(i,0,n){
    FOR(j,0,m){
      int bi=(i+n-1)%n,bj=(j+m-1)%m;
      int ni=(i+1)%n,nj=(j+1)%m;
      if(ccw(a[i],b[j],a[ni])!=-1 && ccw(a[i],b[j],a[bi])!=-1 &&
         ccw(a[i],b[j],b[nj])!=-1 && ccw(a[i],b[j],b[bj])!=-1 ){
        res.pb(Line(a[i],b[j]));
      }
      if(ccw(a[i],b[j],a[ni])!=1 && ccw(a[i],b[j],a[bi])!=1 &&
         ccw(a[i],b[j],b[nj])!=1 && ccw(a[i],b[j],b[bj])!=1){
        res.pb(Line(a[i],b[j]));
      }
      if(ccw(a[i],b[j],a[ni])!=1 && ccw(a[i],b[j],a[bi])!=1 &&
         ccw(a[i],b[j],b[nj])!=-1 && ccw(a[i],b[j],b[bj])!=-1 ){
        res.pb(Line(a[i],b[j]));
      }
      if(ccw(a[i],b[j],a[ni])!=-1 && ccw(a[i],b[j],a[bi])!=-1 &&
         ccw(a[i],b[j],b[nj])!=1 && ccw(a[i],b[j],b[bj])!=1){
        res.pb(Line(a[i],b[j]));
      }
    }
  }
  return res;
}

int n;
Polygon p;

bool check(Segment a){
  if(contains(p,a.p1)==0)return false;
  if(contains(p,a.p2)==0)return false;
  vector<pair<double,Point> > vdp;
  vdp.pb(mp(0,a.p1));
  vdp.pb(mp(abs(a.p1-a.p2),a.p2));
  FOR(i,0,n){
    Segment b(p[i],p[(i+1)%n]);
    if(isParallel(a,b))continue;
    if(!intersect(a,b))continue;
    Point c=getCrossPointLL(a,b);
    vdp.pb(mp(abs(a.p1-c),c));
  }
  sort(all(vdp));
  FOR(i,0,vdp.size()-1){
    Point c=vdp[i].s,d=vdp[i+1].s;
    if(c==d)continue;
    Point m=c+(d-c)/2.0;
    if(contains(p,m)==0)return false;
  }
  return true;
}

double get(Polygon s,Line l){
  vector<Point> vp;
  FOR(i,0,s.size()){
    Point a=s[i],b=s[(i+1)%s.size()];
    if(isParallel(l,Segment(a,b)))continue;
    if(!intersectLS(l,Segment(a,b)))continue;
    Point c=getCrossPointLL(l,Segment(a,b));
    if(!(c==b))vp.pb(c);
  }
  double res=0;
  FOR(i,0,vp.size()){
    FOR(j,i+1,vp.size()){
      
     // pd(abs(vp[i]-vp[j]));
      if(check(Segment(vp[i],vp[j])))res=max(res,abs(vp[i]-vp[j]));
    }
  }
  return res;
}

double solve(){
  double res=0.0;
  FOR(i,0,n)res=max(res,abs(p[i]-p[(i+1)%n]));

  FOR(i,0,n-2){
    FOR(j,i+2,n){
      if((j+1)%n==i)continue;
      Polygon R,L,s;
      s.pb(p[i]);
      s.pb(p[(i+1)%n]);
      s.pb(p[j]);
      s.pb(p[(j+1)%n]);
      Segment s1(s[0],s[3]),s2(s[1],s[2]);
      if(intersect(s1,s2))swap(s1.p2,s2.p2);
      bool flag=true;
      for(int k=(i+1)%n;k!=j;k=(k+1)%n){
        Segment seg=Segment(p[k],p[(k+1)%n]);
        if(isParallel(s1,seg))continue;
        if(!intersect(s1,seg))continue;
        Point tmp=getCrossPointLL(s1,seg);
        if(!(tmp==seg.p1) && !(tmp==seg.p2))flag=false;
      }
      for(int k=(j+1)%n;k!=i;k=(k+1)%n){
        Segment seg=Segment(p[k],p[(k+1)%n]);
        if(isParallel(s2,seg))continue;
        if(!intersect(s2,seg))continue;
        Point tmp=getCrossPointLL(s2,seg);
        if(!(tmp==seg.p1) && !(tmp==seg.p2))flag=false;
      }
      //if(!flag)continue;

      s=convex_hull(s); 

      for(int k=(i+1)%n;k!=(j+1)%n;k=(k+1)%n)
        if(contains(s,p[k])!=0)R.pb(p[k]);
      for(int k=(j+1)%n;k!=(i+1)%n;k=(k+1)%n)
        if(contains(s,p[k])!=0)L.pb(p[k]);
      R=convex_hull(R);
      L=convex_hull(L);
      vector<Line> vs = getTangent(R,L);
      FOR(k,0,R.size()){
        res=max(res,get(s,Segment(R[k],R[(k+1)%R.size()])));
      }
      FOR(k,0,L.size()){
        res=max(res,get(s,Segment(L[k],L[(k+1)%L.size()])));
      }
      FOR(k,0,vs.size()){
        res=max(res,get(s,vs[k]));
      }
    }
  }
  return res;
}

int main()
{
  int c=1;
  while(cin>>n && n){
    p.clear();
    FOR(i,0,n){
      int x,y;
      cin>>x>>y;
      p.pb(Point(x,y));
    }
    cout<<"Case "<<c<<": ";
    pd(solve());
    c++;
  }
  return 0;
}