#include<iostream>
#include<cstdio>
#include<cmath>
#include<map>
#include<algorithm>
#include<vector>
#include<cmath>
#include<random>
#define N 1000000
#define M 1048575
#define Base 13131
#define eps 1e-9
using namespace std;
mt19937 RAND(random_device{}());
int read()
{
    char c=0;
    int sum=0;
    while (c<'0'||c>'9') c=getchar();
    while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
    return sum;
}
struct points
{
    int x,y;
    bool operator != (const points &t)const
   	{
		return x!=t.x&&y!=t.y;    
	}
};
points st[N+1];
double dist(points a,points b)
{
    return sqrt(1ll*(a.x-b.x)*(a.x-b.x)+1ll*(a.y-b.y)*(a.y-b.y));
}
struct node
{
    int x,y,data,nxt;
};
node edge[N+1];
int T,n,len,head[M+1],length,tong[N+1],leng;
double ans,tans;
vector<points>v[N+1];
void add(int x,int y,int d)
{
    int ds=(x+y)&M;
    edge[++len]=(node){x,y,d,head[ds]},head[ds]=len,tong[++leng]=ds;
    return;
}
int query(int x,int y)
{
    int ds=(x+y)&M;
    for (int i=head[ds];i>0;i=edge[i].nxt)
		if (edge[i].x==x&&edge[i].y==y)
			return edge[i].data;
    return -1;
}
void build(int x,double d)
{
    int ps;
    for (int i=1;i<=leng;++i) head[tong[i]]=0;
    len=length=leng=0;
    for (int i=1;i<=x;++i)
    {
		ps=query((int)(floor(st[i].x/d)),(int)(floor(st[i].y/d)));
		if (ps==-1) add((int)(floor(st[i].x/d)),(int)(floor(st[i].y/d)),++length),ps=length,v[length].clear();
		v[ps].push_back(st[i]);
    }
    return;
}
int main()
{
    bool opt;
    int ps,ps2;
	T=read();
	for (int qt=1;qt<=T;++qt)
	{
		len=leng=ans=0;
		for (int i=0;i<=M;++i) head[i]=0;
    	n=read();
    	for (int i=1;i<=n;++i) st[i].x=read(),st[i].y=read();
    	shuffle(st+1,st+n+1,RAND),ans=dist(st[1],st[2])+dist(st[1],st[3])+dist(st[2],st[3]),build(2,ans);
    	for (int i=4;i<=n;++i)
    	{
			opt=0,tans=ans;
			for (int op=-1;op<=1;++op)
				for (int op2=-1;op2<=1;++op2)
					if (query((int)(floor(st[i].x/tans)+op),(int)(floor(st[i].y/tans)+op2))!=-1)
					{
						ps=query((int)(floor(st[i].x/tans))+op,(int)(floor(st[i].y/tans))+op2);
						for (int op3=-1;op3<=1;++op3)
							for (int op4=-1;op4<=1;++op4)
								if ((op<op3||(op==op3&&op2<=op4))&&query((int)(floor(st[i].x/tans)+op3),(int)(floor(st[i].y/tans)+op4))!=-1)
								{
									ps2=query((int)(floor(st[i].x/tans))+op3,(int)(floor(st[i].y/tans))+op4);
									for (int j=0;j<v[ps].size();++j)
										for (int k=0;k<v[ps2].size();++k)
											if (v[ps][j]!=v[ps2][k]&&dist(st[i],v[ps][j])+dist(st[i],v[ps2][k])+dist(v[ps][j],v[ps2][k])+eps<ans)
												ans=dist(st[i],v[ps][j])+dist(st[i],v[ps2][k])+dist(v[ps][j],v[ps2][k]),opt=1;
								}
					}
			if (opt) build(i,ans);
			else
			{
				ps=query((int)(floor(st[i].x/ans)),(int)(floor(st[i].y/ans)));
				if (ps==-1) add((int)(floor(st[i].x/ans)),(int)(floor(st[i].y/ans)),++length),ps=length,v[length].clear();
				v[ps].push_back(st[i]);
			}
		}
		printf("Case #d: %0.9lf\n",ans);
	}
	return 0;
}