#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=

MgozIDUKMSA1CjEwIDExCjggOQozIDIKMSAyCjMgNQoxMyAxOA==

2
3 5
1 5
10 11
8 9
3 2
1 2
3 5
13 18