#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#define LL __int64

using namespace std;

const int maxn=;

const int maxc=;

const int maxr=;

const int inf=0x3f3f3f3f;

const double rinf=1e10;

int L[maxn], R[maxn], D[maxn], U[maxn], C[maxn];

int S[maxc], H[maxr], size;

int N,M,K;

struct City{

    LL x,y;

}cities[maxr];

struct Radar{

    int x,y;

}radar[maxc];

LL map[][];

///²»ÐèÒªSÓò

void Link(int r, int c)

{

    S[c]++; C[size]=c;

    U[size]=U[c]; D[U[c]]=size;

    D[size]=c; U[c]=size;

    if(H[r]==-) H[r]=L[size]=R[size]=size;

    else {

        L[size]=L[H[r]]; R[L[H[r]]]=size;

        R[size]=H[r]; L[H[r]]=size;

    }

    size++;

}

void remove(int c){

    for (int i=D[c]; i!=c; i=D[i])

        L[R[i]]=L[i], R[L[i]]=R[i];

}

void resume(int c){

    for (int i=U[c]; i!=c; i=U[i])

        L[R[i]]=R[L[i]]=i;

}

int h(){///Óþ«È·¸²¸ÇÈ¥¹ÀËã¼ôÖ¦

    int ret=;

    bool vis[maxc];

    memset (vis, false, sizeof(vis));

    for (int i=R[]; i; i=R[i])

    {

        if(vis[i])continue;

        ret++;

        vis[i]=true;

        for (int j=D[i]; j!=i; j=D[j])

            for (int k=R[j]; k!=j; k=R[k])

                vis[C[k]]=true;

    }

    return ret;

}

int ans;

bool Dance(int k){

    int t=h();

     if(t+k>M) return false;                //¸ù¾Ý¾ßÌåÎÊÌâÑ¡ÔñÏÞÖÆËÑË÷Éî¶È»òÖ±½ÓÇó½â¡£  A*Ëã·¨£¬´Ë´¦Ö»Çó×îÓŽâ

    if(!R[]){

        return true;

    }

    int c=R[];

    for (int i=R[]; i; i=R[i])

        if(S[i]<S[c])c=i;

    for (int i=D[c]; i!=c; i=D[i]){

        remove(i);

        for (int j=R[i]; j!=i; j=R[j])

            remove(j);

        if(Dance(k+)) return true;

        for (int j=L[i]; j!=i; j=L[j])

            resume(j);

        resume(i);

    }

    return false;

}

void initL(int x){///col is 1~x,row start from 1

//    ans=inf;

    for (int i=; i<=x; ++i){

        S[i]=;

        D[i]=U[i]=i;

        L[i+]=i; R[i]=i+;

    }///¶ÔÁбíÍ·³õʼ»¯

    R[x]=;

    size=x+;///ÕæÕýµÄÔªËØ´Óm+1¿ªÊ¼

    memset (H, -, sizeof(H));

    ///markÿ¸öλÖõÄÃû×Ö

}

LL dabs(LL a){

    if(a<) return -a;

    return a;

}

LL dist(int i,int j){

    return (dabs(cities[i].x-cities[j].x)+dabs(cities[i].y-cities[j].y));

}

void BuildLink(LL r){

    for(int i=;i<=N;i++){

        for(int j=;j<=N;j++){

            if(map[i][j]<=r)

            Link(i,j);

        }

    }

}

void bin(){

    LL Ans;

    LL l=,r=20000000050ll,m;

    ans=inf;

    while(l<=r){

        m=(l+r)/2ll;

        ans=inf;

        initL(N);

        BuildLink(m);

        if(Dance())

        { Ans=m; r=m-; }

        else l=m+;

    }

    printf("%I64d\n",Ans);

}

int main(){

    int T,t=;

    scanf("%d",&T);

    while(T--){

        scanf("%d%d",&N,&M);

        for(int i=;i<=N;i++)

        scanf("%I64d%I64d",&cities[i].x,&cities[i].y);

        for(int i=;i<=N;i++){

            for(int j=;j<=N;j++){

            map[i][j]=dist(i,j);

    //    cout<<map[i][j]<<" ";

            }

        //    cout<<endl;

        }

        printf("Case #%d: ",++t);

/*        if(M==0){

            cout<<"Yes"<<endl;

            int Ans=inf;

            for(int i=2;i<=N;i++){

                if(map[1][i]<Ans) Ans=map[1][i];

            }

            printf("%d\n",Ans);

        }

        else*/

        bin();

    }

    return ;

}