#include <bits/stdc++.h>
typedef long long int ll;
using namespace std;
int main() {
ll test;
cin>>test;
for(ll t=1;t<=test;t++)
{
ll n, k;
cin>>n>>k;
vector< pair<ll,ll> > a;
for(int i=0;i<n;i++)
{
ll start, end;
cin>>start>>end;
a.push_back(make_pair(start, end));
}
stable_sort(a.begin(), a.end());
cout<<"Case #"<<t<<": ";
ll curr=0, count=0;
for(int i=0;i<n;i++)
{
if(curr<a[i].second)
{
count++;
curr = max(curr, a[i].first) + k;
}
}
ll rem=a.back().second-curr;
if(rem>0)
{
count+=rem/k;
if(rem%k)
count++;
}
cout<<count<<endl;
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnR5cGVkZWYgbG9uZyBsb25nIGludCBsbDsKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBtYWluKCkgewoJbGwgdGVzdDsKCWNpbj4+dGVzdDsKCWZvcihsbCB0PTE7dDw9dGVzdDt0KyspCgl7CglsbCBuLCBrOwoJY2luPj5uPj5rOwoJdmVjdG9yPCBwYWlyPGxsLGxsPiA+IGE7Cglmb3IoaW50IGk9MDtpPG47aSsrKQoJewoJCWxsIHN0YXJ0LCBlbmQ7CgkJY2luPj5zdGFydD4+ZW5kOwoJCWEucHVzaF9iYWNrKG1ha2VfcGFpcihzdGFydCwgZW5kKSk7Cgl9CglzdGFibGVfc29ydChhLmJlZ2luKCksIGEuZW5kKCkpOwoJCgljb3V0PDwiQ2FzZSAjIjw8dDw8IjogIjsKCWxsIGN1cnI9MCwgY291bnQ9MDsKCWZvcihpbnQgaT0wO2k8bjtpKyspCgl7CgkJaWYoY3VycjxhW2ldLnNlY29uZCkKCQl7CgkJCWNvdW50Kys7CgkJCQoJCQljdXJyID0gbWF4KGN1cnIsIGFbaV0uZmlyc3QpICsgazsKCQl9Cgl9CgkKCWxsIHJlbT1hLmJhY2soKS5zZWNvbmQtY3VycjsKCWlmKHJlbT4wKQoJewoJCWNvdW50Kz1yZW0vazsKCQlpZihyZW0laykKCQkJY291bnQrKzsKCQl9Cgljb3V0PDxjb3VudDw8ZW5kbDsKCX0KCQoJcmV0dXJuIDA7Cn0=