#include <bits/stdc++.h>
#define int long long
#define mk make_pair
#define PII pair<int,int>
#define FOR(i,j,k) for(int i=(j);i<=(k);++i)
#define ROF(i,j,k) for(int i=(j);i>=(k);--i)
#define FOI(a,b) for(auto a : b)
#define wh while
#define inf 0x3f3f3f3f3f3f3f3f
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define snd second
#define fst first
#define pb push_back
#define CI const int
#define NP namespace
using NP std;
int quickpow(int a,int b)
{
	int ans=1;
	wh(b)
	{
		if(b&1)ans=ans*a;
        a=a*a;
		b>>=1;
	}
	return ans;
}
CI MAXN=1e5+5;
int l[MAXN],r[MAXN],n,m,cnt=0,ans=0; 
vector<PII> d,c; 
void solve()
{
	d.clear();
	c.clear();
	ans=0,cnt=0;
	cin>>n>>m;
	FOR(i,1,n)
	{
		cin>>l[i]>>r[i];
		d.pb({l[i]+1,1});
		d.pb({r[i],-1});
	}
	sort(d.begin(),d.end());
	int last=0;
	FOI(x,d)
	{ 
		if(last!=x.fst)
		{
			int len=x.fst-last;
			c.pb({cnt,len});
			last=x.fst;
		}
		cnt+=x.snd;
	}
	sort(c.begin(),c.end());
	reverse(c.begin(),c.end());
	FOI(s,c)
	{
		if(m>=s.snd)
		{
			m-=s.snd;
			ans+=s.fst*s.snd;
		}
		else
		{
			ans+=m*s.fst;
			break;
		}
	}
}
signed main(void)
{
    freopen("slicing.in","r",stdin);
    freopen("slicing.out","w",stdout);
	IOS
	int t;
	cin>>t;
	FOR(i,1,t)
	{
		solve();
		cout<<"Case #"<<i<<": "<<ans+n<<"\n";
	}
    return false;
}