#include<iostream>
#include<string.h>
#include<stdio.h>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<math.h>
#include<set>
#include<bitset>
#include<deque>
#include<unordered_map>
#include<algorithm>
#define int long long
using namespace std;
const int N = 1e6 + 10, M = 1e8 + 10;
const int mod = 998244353;
int n,k;
struct cs
{
	int x,y;
}c[N];
bool cmp(cs d1,cs d2)
{
	if(d1.x==d2.x)return d1.y<d2.y;
	return d1.x<d2.x;
}
void df() {
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>c[i].x>>c[i].y;
	if(k==1)
	{
		cout<<n<<endl;
		return;
	}
	sort(c+1,c+1+n,cmp);
	priority_queue<int,vector<int>,greater<int>>q;
	q.push(c[1].y);
	int ans=0,nu=0;
	for(int i=2;i<=n;i++)
	{
		nu=0;
		int kl=0;
		while(q.empty()!=1)
		{
			int tt=q.top();
			if(c[i].x<=tt)//能相交的
			{
				int jk=q.size();
				int mn=min(nu,jk);
				if(nu!=0)
				{
					ans++;
					kl=0;
				}
				while(mn--)q.pop();
				break;
			}
			q.pop();
			kl++;
			if(kl==k)
			{
				ans++;
				nu=0,kl=0;
			}
			else
				nu=k-kl;
		}
		if(kl!=0)ans++;
		q.push(c[i].y);
//		cout<<i<<"[[[";
//		cout<<nu<<" "<<kl<<" ";
//		cout<<ans<<endl;
	}
	if(q.empty()!=1)
	{
		int tt=q.size();
		ans+=tt/k;
		if(tt%k)ans++;
	}
	cout<<ans<<endl;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie();
	cout.tie();
	int t = 1;
	cin >> t;
	while (t--) {
		df();
	}
	return 0;
}