#include<bits/stdc++.h>
using namespace std;
int main(){
long long int test, i, j, n, k;
scanf("%lld", &test);
for(i=1;i<=test;i++){
scanf("%lld%lld", &n, &k);
vector<pair<long long int,long long int> > v;
for(j=0;j<n;j++){
long long int start, end;
scanf("%lld%lld", &start, &end);
v.push_back(make_pair(start, end));
}
sort(v.begin(), v.end());
long long int ans = 0, t = 0;
j = 0;
while(j<n){
if(t<=v[j].first){
t = v[j].first + k;
ans++;
} else if(t<v[j].second){
t = t+k;
ans++;
} else{
j++;
}
}
cout << "case #" << i << ": " << ans << "\n";
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBtYWluKCl7CiAgICBsb25nIGxvbmcgaW50IHRlc3QsIGksIGosIG4sIGs7CiAgICBzY2FuZigiJWxsZCIsICZ0ZXN0KTsKICAgIGZvcihpPTE7aTw9dGVzdDtpKyspewogICAgICAgIHNjYW5mKCIlbGxkJWxsZCIsICZuLCAmayk7CiAgICAgICAgdmVjdG9yPHBhaXI8bG9uZyBsb25nIGludCxsb25nIGxvbmcgaW50PiA+IHY7CiAgICAgICAgZm9yKGo9MDtqPG47aisrKXsKICAgICAgICAgICAgbG9uZyBsb25nIGludCBzdGFydCwgZW5kOwogICAgICAgICAgICBzY2FuZigiJWxsZCVsbGQiLCAmc3RhcnQsICZlbmQpOwogICAgICAgICAgICB2LnB1c2hfYmFjayhtYWtlX3BhaXIoc3RhcnQsIGVuZCkpOwogICAgICAgIH0KICAgICAgICBzb3J0KHYuYmVnaW4oKSwgdi5lbmQoKSk7CiAgICAgICAgbG9uZyBsb25nIGludCBhbnMgPSAwLCB0ID0gMDsKICAgICAgICBqID0gMDsKICAgICAgICB3aGlsZShqPG4pewogICAgICAgICAgICBpZih0PD12W2pdLmZpcnN0KXsKICAgICAgICAgICAgICAgIHQgPSB2W2pdLmZpcnN0ICsgazsKICAgICAgICAgICAgICAgIGFucysrOwogICAgICAgICAgICB9IGVsc2UgaWYodDx2W2pdLnNlY29uZCl7CiAgICAgICAgICAgICAgICB0ID0gdCtrOwogICAgICAgICAgICAgICAgYW5zKys7CiAgICAgICAgICAgIH0gZWxzZXsKICAgICAgICAgICAgICAgIGorKzsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBjb3V0IDw8ICJjYXNlICMiIDw8IGkgPDwgIjogIiA8PCBhbnMgPDwgIlxuIjsKICAgIH0KICAgIHJldHVybiAwOwp9