const int INF=1000000005;const int N=4444;int m;struct node{	int L[N],R[N],D[N],U[N],e;	int col[N];	int H[N],num[N];	int visit[N],KK;	void init(int n)	{		KK=0;		int i;		for(i=0;i<=n;i++)		{			if(i==n) L[i]=0;			else L[i]=i+1;			if(i==0) R[i]=n;			else R[i]=i-1;			num[i]=0;			H[i]=-1;			D[i]=U[i]=i;		}		e=n+1;	}	void add(int r,int c)	{		U[e]=c;		D[e]=D[c];		U[D[c]]=e;		D[c]=e;		if(H[r]<0) H[r]=L[e]=R[e]=e;		else		{			L[e]=L[H[r]];			R[e]=H[r];			R[L[H[r]]]=e;			L[H[r]]=e;		}		num[c]++;		col[e]=c;		e++;	}	void remove(int c)	{		int i;		for(i=D[c];i!=c;i=D[i])		{			R[L[i]]=R[i];			L[R[i]]=L[i];		}	}	void resume(int c)	{		int i;		for(i=U[c];i!=c;i=U[i])		{			L[R[i]]=R[L[i]]=i;		}	}	int astar()	{		KK++;		int ans=0,i,j,k;		for(i=L[0];i!=0;i=L[i]) if(KK!=visit[i])		{			visit[i]=KK;			ans++;			for(j=D[i];j!=i;j=D[j]) for(k=L[j];k!=j;k=L[k])			{				visit[col[k]]=KK;			}		}		return ans;	}	int DFS(int cnt)	{		if(L[0]==0) return 1;		if(cnt+astar()>m) return 0;		int tmp=INF,c,i;		for(i=L[0];i!=0;i=L[i]) if(num[col[i]]<tmp)		{			tmp=num[col[i]];			c=i;		}		for(i=D[c];i!=c;i=D[i])		{			remove(i);			int j;			for(j=L[i];j!=i;j=L[j]) remove(j);			if(DFS(cnt+1)) return 1;			for(j=R[i];j!=i;j=R[j]) resume(j);			resume(i);		}		return 0;	}}A;int a[66][2];i64 dis[66][66];int n;i64 d[4444];inline i64 dist(int i,int j){	return ((i64)abs(a[i][0]-a[j][0]))+abs(a[i][1]-a[j][1]);}int ok(i64 M){	A.init(n);	int i,j;	for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(dis[i][j]<=M)	{		A.add(i,j);	}	return A.DFS(0);}i64 cal(){	int num=0;	int i,j;	for(i=1;i<=n;i++) for(j=1;j<=n;j++) dis[i][j]=dist(i,j),d[num++]=dis[i][j];	sort(d,d+num);	int M=unique(d,d+num)-d;	int low=0,high=M-1;	i64 ans=0;	while(low<=high)	{		int mid=(low+high)>>1;		if(ok(d[mid])) ans=d[mid],high=mid-1;		else low=mid+1;	}	return ans;}int main(){	int num=0;	int T=getInt();	while(T--)	{		n=getInt();		m=getInt();		int i;		for(i=1;i<=n;i++) scanf("%d%d",&a[i][0],&a[i][1]);		printf("Case #%d: ",++num);		cout<<cal()<<endl;	}}