#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
#define N 5000
using namespace std;
int read()
{
    char c=0;
    int sum=0,f=1;
    while (c!='-'&&(c<'0'||c>'9')) c=getchar();
    if (c=='-') c=getchar(),f=-1;
    while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
    return sum*f;
}
struct points
{
    long long x,y;
    bool operator < (const points &t)const
    {
	return (x!=t.x)?x<t.x:y<t.y;    
    }
};
points st[N+1],dque[N+1];
vector<points>A;
vector<points>B;
vector<points>C;
vector<points>D;
vector<points>res;
int T,n,m,sm,top;
bool check(points a,points b,points c)
{
    return (b.y-a.y)*(c.x-a.x)<=(c.y-a.y)*(b.x-a.x);
}
vector<points>operator + (vector<points>a,vector<points>b)
{
    vector<points>c;
    for (int i=0;i<a.size();++i)
	for (int j=0;j<b.size();++j)
	    c.push_back((points){a[i].x+b[j].x,a[i].y+b[j].y});
    return c;
}
vector<points>solve(vector<points>p)
{
    vector<points>st;
    sort(p.begin(),p.end()),top=0;
    for (int i=0;i<p.size();++i)
    {
	while (top>=2&&check(dque[top-1],dque[top],p[i])) top--;
	st.push_back(p[i]),dque[++top]=p[i];
    }
    top=0;
    for (int i=(int)(p.size())-1;i>=0;--i)
    {
	while (top>=2&&check(dque[top-1],p[i],dque[top])) top--;
	if (i&&i+1!=p.size()) st.push_back(p[i]);
	dque[++top]=p[i];
    }
    return st;
}
int main()
{
    int x,y;
    double ans;
    T=read();
    for (int qt=1;qt<=T;++qt)
    {
	n=read(),m=read(),ans=0;
	for (int i=1;i<=n;++i) x=read(),y=read(),st[i].x=x-y,st[i].y=x+y;
	for (int w=0;w<=min(3,m);++w)
	{
	    sm=m-w,A.clear(),B.clear(),C.clear(),D.clear();
	    for (int i=1;i<=n;++i)
	    {
		A.push_back((points){st[i].x*((sm+3)>>2),st[i].y*((sm+3)>>2)});
		B.push_back((points){st[i].y*((sm+2)>>2),-st[i].x*((sm+2)>>2)});
		C.push_back((points){-st[i].x*((sm+1)>>2),-st[i].y*((sm+1)>>2)});
		D.push_back((points){-st[i].y*(sm>>2),st[i].x*(sm>>2)});
	    }
	    A=solve(A),B=solve(B),C=solve(C),D=solve(D),res=A,res=solve(res+B),res=solve(res+C),res=solve(res+D);
	    for (int i=0;i<res.size();++i) ans=max(ans,sqrt(res[i].x*res[i].x+res[i].y*res[i].y));
	}
	printf("Case #%d: %0.10lf\n",qt,ans);
    }
    return 0;
}