#include<iostream>
#include<cstdio>
#include<string.h>
#include<vector>
#include<math.h>
#include<algorithm>
#define inf 0x3fffffff
using namespace std;
struct node{
	int x,y;
};
const int N = 64;
const int M = 64*64;
int U[M], D[M], R[M], L[M], rs[N];
int size[N], head, row[M], col[M];
vector<long long> dist;
int n, m, k;
int nodecnt, ans;
int LIMIT;
void init(int m) {  /* m是列的数量 */
    memset(size, 0, sizeof (size));
    memset(col, -1, sizeof (col));
    nodecnt = m + 1;
    for (int i = 0; i <= m; i++) {
        L[i] = (i - 1);
        R[i] = (i + 1);
        col[i] = i;
        D[i] = U[i] = i;
    }
    L[0] = m;
    R[m] = 0;
    size[0] = inf;
}
inline void Remove(int x) {
    for (int i = D[x]; i != x; i = D[i]) {
        L[ R[i] ] = L[i];
        R[ L[i] ] = R[i];
        size[ col[i] ]--;
    }
}
inline void Resume(int x) {
    for (int i = U[x]; i != x; i = U[i]) {
        L[ R[i] ] = R[ L[i] ] = i;
        size[ col[i] ]++;
    }
}
inline int evalute() { /* 估价函数 */
    bool vis[M] = {false};
    int tt = 0;
    for (int i = R[0]; i != 0; i = R[i])
        if (!vis[col[i]]) {
            tt++;
            vis[col[i]] = true;
            for (int j = D[i]; j != i; j = D[j])
                if (col[j] != 0)
                    for (int k = R[j]; k != j; k = R[k]) vis[ col[k] ] = true;
        }
    return tt;
}
bool dfs(int num) {  /*这里的dfs是一个迭代加深的过程*/
    if (num + evalute() > LIMIT) return 0;
    if (R[0] == 0) return 1;
    int i, j, opt = 0;
    for (i = R[0]; i != 0; i = R[i])
        if (size[col[i]] < size[col[opt]]) {
            opt = i;
            if (size[col[i]] <= 1) break;
        }
    for (i = D[opt]; i != opt; i = D[i]) {
        Remove(i);
        for (j = R[i]; i != j; j = R[j]) Remove(j);
        if (dfs(num + 1)) return 1;
        for (j = L[i]; j != i; j = L[j]) Resume(j);
        Resume(i);
    }
    return 0;
}
inline void insert(int i, int *tt, int c) {
    for (int j = 0; j < c; j++, nodecnt++) {
        int x = tt[j];
        row[nodecnt] = i;
        col[nodecnt] = x;
        size[x]++;
        U[nodecnt] = x;
        D[nodecnt] = D[x];
        U[D[x]] = nodecnt;
        D[x] = nodecnt;
        if (j == 0) L[nodecnt] = R[nodecnt] = nodecnt;
        else {
            L[nodecnt] = nodecnt - 1;
            R[nodecnt] = nodecnt - j;
            R[nodecnt - 1] = nodecnt;
            L[nodecnt - j] = nodecnt;
        }
    }
}
node point[N];
long long CALC(node a,node b){
	long long t1,t2;
	t1=fabs(b.x-a.x);
	t2=fabs(b.y-a.y);
	return t1+t2;
}
bool ori[N][N];
void build(long long d) {
	memset(ori,0,sizeof(ori));
	/* build matrix */
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			long long t=CALC(point[i],point[j]);
			if(t<=d)	ori[i][j]=1;
			else		ori[i][j]=0;
		}
	int tt[N],c=0;
	int t=n+1;
	for(int i=1;i<t;i++){		/* 扫一遍所有的行，检查每一行的 1 */  
		c=0;
		for(int j=1;j<t;j++)
			if(ori[i][j]==1)	tt[c++]=j;
		insert(i,tt,c);		/*插入，tt 数组里面是 01 矩阵里每一行里面1所在的列，c 为 1 的个数*/  
	}
	return ;
}
inline bool cmp(long long a,long long b){
	return a<b;
}
void read(){
	scanf("%d%d",&n,&LIMIT);
	dist.clear();
	for(int i=1;i<=n;i++)
		scanf("%d%d",&point[i].x,&point[i].y);
	for(int i=1;i<n;i++)
		for(int j=i+1;j<=n;j++){
			long long t=CALC(point[i],point[j]);
			dist.push_back(t);
		}
	sort(dist.begin(),dist.end(),cmp);
	return ;
}
int main() {
	int T;
	scanf("%d",&T);
    for(int ppp=1;ppp<=T;ppp++){  
		read();
        int left=-1,right=dist.size()-1,mid;
		while(left+1<right){
			init(n);
			mid=(left+right)/2;
			build(dist[mid]);    
			if(dfs(0))
				right=mid;
			else	left=mid;
		}
		printf("Case #%d: %I64d\n",ppp,dist[right]);
    }
    return 0;
}