#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
 
int32_t main()
{
	IOS;
	int t;
	cin >> t;
	int tc = 0; 
	while(t--)
	{
		tc++;
		int n,k,i,x,y,limit=0;
		cin>>n>>k;
		vector<pair<int,int>>arr;
		for(i=0;i<n;i++){
		    cin>>x>>y;
		    arr.push_back({x,y});
		 }   
		 sort(arr.begin(),arr.end());
		 int ans=0;
		 i=0;
		 limit=arr[0].first;
		 while(i<n){
			 //cout<<limit<<endl;
		     limit=limit + k;
		     ans++;
		     while(i<n && limit>=arr[i].second)
		        i++;
		     if(i<n && limit<arr[i].first){
		         limit=arr[i].first;
		     }
		 }
		cout << "Case #" << tc << ": " << ans << endl;
 	}	
	return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgSU9TIGlvczo6c3luY193aXRoX3N0ZGlvKDApOyBjaW4udGllKDApOyBjb3V0LnRpZSgwKTsKI2RlZmluZSBpbnQgbG9uZyBsb25nCgppbnQzMl90IG1haW4oKQp7CglJT1M7CglpbnQgdDsKCWNpbiA+PiB0OwoJaW50IHRjID0gMDsgCgl3aGlsZSh0LS0pCgl7CgkJdGMrKzsKCQlpbnQgbixrLGkseCx5LGxpbWl0PTA7CgkJY2luPj5uPj5rOwoJCXZlY3RvcjxwYWlyPGludCxpbnQ+PmFycjsKCQlmb3IoaT0wO2k8bjtpKyspewoJCSAgICBjaW4+Png+Pnk7CgkJICAgIGFyci5wdXNoX2JhY2soe3gseX0pOwoJCSB9ICAgCgkJIHNvcnQoYXJyLmJlZ2luKCksYXJyLmVuZCgpKTsKCQkgaW50IGFucz0wOwoJCSBpPTA7CgkJIGxpbWl0PWFyclswXS5maXJzdDsKCQkgd2hpbGUoaTxuKXsKCQkJIC8vY291dDw8bGltaXQ8PGVuZGw7CgkJICAgICBsaW1pdD1saW1pdCArIGs7CgkJICAgICBhbnMrKzsKCQkgICAgIHdoaWxlKGk8biAmJiBsaW1pdD49YXJyW2ldLnNlY29uZCkKCQkgICAgICAgIGkrKzsKCQkgICAgIGlmKGk8biAmJiBsaW1pdDxhcnJbaV0uZmlyc3QpewoJCSAgICAgICAgIGxpbWl0PWFycltpXS5maXJzdDsKCQkgICAgIH0KCQkgfQoJCWNvdXQgPDwgIkNhc2UgIyIgPDwgdGMgPDwgIjogIiA8PCBhbnMgPDwgZW5kbDsKIAl9CQoJcmV0dXJuIDA7Cn0=

MwozIDUKMSA1CjEwIDExCjggOQozIDIKMSAyCjMgNQoxMyAxNAoyIDEwCjEgMTAKNSAyMA==

3
3 5
1 5
10 11
8 9
3 2
1 2
3 5
13 14
2 10
1 10
5 20