#include<bits/stdc++.h>
using namespace std;
struct node
{
    int a;
    int b;
};
vector<node >v;
int main()
{
    int t,c=0;
    scanf("%d",&t);
    while(t--){
        set<long int>s;
        set<long int>::iterator it;
        set<long int>::iterator j;
        c++;
        v.clear();
        long int n,p,i,k;
        scanf("%ld%ld",&n,&p);
        int m=0;
        for(i=0;i<n;i++){
            node x;
            scanf("%ld%ld",&x.a,&x.b);
            s.insert(x.a);
            s.insert(x.b);
            v.push_back(x);
        }
        int cnt=0;
        long int ans=INT_MAX;
        for(it=s.begin();it!=s.end();it++){
            //cnt=0;
            for(j=it;j!=s.end();j++){
                cnt=0;
                for(k=0;k<v.size();k++){
                    if(v[k].a<=*it && v[k].b>=*it){
                        cnt++;
                        //cout<<v[k].a<< " "<<v[k].b<<endl;
                    }
                    else if(v[k].a<=*j && v[k].b>=*j){
                        cnt++;
                        //cout<<v[k].a<< " "<<v[k].b<<endl;
                    }
                }
                //if(*j==8 && *it==7) cout<<cnt<<endl;
                if(cnt>=p) {
                    ans=min(ans,*j-*it);
                //cout<<*j<<" "<<*it<<" "<<ans<<endl;
                }
            }
        }
        printf("Case %ld: %ld\n",c,ans);
        s.clear();
    }
}