#include <bits/stdc++.h>

using namespace std;

using u32=unsigned int;
using i64=long long;
using u64=unsigned long long;
using db=double;
using vi=vector<int>;
using pii=pair<int,int>;

template<typename T>
T read(){
    T x=0,f=0;char ch=getchar();
    while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();
    while(isdigit(ch)) x=x*10+(ch-'0'),ch=getchar();
    return f?-x:x;
}

#define rdi read<int>
#define rdi64 read<i64>
#define fi first
#define se second
#define pb push_back

const int N=5010,INF=0x3f3f3f3f;
const int MX=2000;

int n,m;

struct vec{
    i64 x,y;
    vec operator+ (const vec &rhs) const{
        return {x+rhs.x,y+rhs.y};
    }
    vec operator- (const vec &rhs) const{
        return {x-rhs.x,y-rhs.y};
    }
    vec operator* (i64 k) const{
        return {x*k,y*k};
    }
    db abs() const{
        return hypot(x,y);
    }
    db arg() const{
        return atan2(y,x);
    }
    i64 cross(const vec &rhs) const{
        return x*rhs.y-y*rhs.x;
    }
    i64 dot(const vec &rhs) const{
        return x*rhs.x+y*rhs.y;
    }
    bool operator== (const vec &rhs) const{
        return x==rhs.x&&y==rhs.y;
    }
    bool operator!= (const vec &rhs) const{
        return !(*this==rhs);
    }
};

vector<vec> convex_hull(const vector<vec> &v){
    static const int M=1e6+10;
    vec mi=*min_element(v.begin(),v.end(),[&](vec a,vec b){
        return a.y!=b.y?a.y<b.y:a.x<b.x;
    });
    static int id[M];
    static db a[M],d[M];
    int sz=v.size();
    for(int i=0;i<sz;i++)
        id[i]=i,a[i]=(v[i]-mi).arg(),d[i]=(v[i]-mi).abs();
    sort(id,id+sz,[&](int x,int y){
        return fabs(a[x]-a[y])>1e-9?a[x]<a[y]:d[x]<d[y];
    });

    static vec st[1<<18|10];int tp=0;
    for(int i=0;i<sz;i++){
        vec cur=v[id[i]];
        while(tp>1&&(st[tp]-st[tp-1]).cross(cur-st[tp])<=0) --tp;
        st[++tp]=cur;
    }
    return {st+1,st+tp+1};
}

vec p[N];

template<typename T>
void ckmin(T &a,T b) {if(a>b) a=b;}
template<typename T>
void ckmax(T &a,T b) {if(a<b) a=b;}

void solve(int tid){
    n=rdi(),m=rdi();
    for(int i=1;i<=n;i++){
        int x=rdi(),y=rdi();
        p[i]={x-y,x+y};
    }
    
    vector<vec> f[5];
    f[0].pb({0,0});
    for(int i=1;i<=4;i++){
        static i64 _mi[MX*8+1],_mx[MX*8+1];
        static i64 *mi=_mi+MX*4,*mx=_mx+MX*4;
        for(int j=-MX*i;j<=MX*i;j++)
            mi[j]=INF,mx[j]=-INF;
        for(int j=1;j<=n;j++){
            vec dt;
            if(i==1) dt={p[j].x,p[j].y};
            else if(i==2) dt={p[j].y,-p[j].x};
            else if(i==3) dt={-p[j].x,-p[j].y};
            else if(i==4) dt={-p[j].y,p[j].x};
            for(auto tmp:f[i-1]){
                vec to=tmp+dt;
                mi[to.x]=min(mi[to.x],to.y);
                mx[to.x]=max(mx[to.x],to.y);
            }
        }
        for(int j=-MX*i;j<=MX*i;j++)
            if(mi[j]!=INF) f[i].pb({j,mi[j]}),f[i].pb({j,mx[j]});
        f[i]=convex_hull(f[i]);
    }

    db ans=0;
    for(int i=1;i<=min(4,m);i++){
        for(auto cur:f[i]){
            ans=max(ans,cur.abs());
            int c=(m-i)/4;
            for(auto cur1:f[4])
                ans=max(ans,(cur+cur1*c).abs());
        }
    }
    printf("Case #%d: %.10lf\n",tid,ans);
}

int main(){
    int T=rdi();
    for(int i=1;i<=T;i++) solve(i);
    return 0;
}