#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll T[400055]={0},U[400055]={0},A[100020]={0};
void build(ll node,ll s,ll e){
if(s==e)
T[node]=0;
else{
ll mid=(s+e)>>1;
build(2*node,s,mid);
build(2*node+1,mid+1,e);
}
}
void update(ll node,ll s,ll e,ll x,ll y,ll val){
if(U[node]!=0){
T[node]+=(e-s+1)*U[node];
if(s!=e){
U[2*node]+=U[node];
U[2*node+1]+=U[node];
}
U[node]=0;
}
if(s>e || s>y || e<x)
return;
if(s>=x && e<=y){
T[node]+=(e-s+1)*val;
if(s!=e){
U[2*node]+=val;
U[2*node+1]+=val;
}
return ;
}
ll mid=(s+e)>>1;
update(2*node,s,mid,x,y,val);
update(2*node+1,mid+1,e,x,y,val);
T[node]=T[2*node]+T[2*node+1];
}
ll find(ll node,ll s,ll e,ll x,ll y){
if(x>e || y<s)
return 0;
if(U[node]!=0){
T[node]+=(e-s+1)*U[node];
if(s!=e){
U[2*node]+=U[node];
U[2*node+1]+=U[node];
}
U[node]=0;
}
if(s>=x && e<=y){
ll x=T[node];
T[node]=U[node]=0;
return x;
}
ll mid=(s+e)>>1;
ll p1=find(2*node,s,mid,x,y);
ll p2=find(2*node+1,mid+1,e,x,y);
T[node]=0;
return p1+p2;
}
int main(){
ll t;
cin>>t;
while(t--){
ll n,k,a,b;
cin>>n>>k;
ll c=INT_MIN;
ll R[n+1],L[n+1];
/*
memset(A,0,sizeof(A));
memset(T,0,sizeof(T));
memset(U,0,sizeof(U));*/
vector<ll> B,C;
for(ll i=0;i<n;i++){
cin>>L[i]>>R[i];
c=max(c,R[i]+3);
}
// build(1,1,c);
for(ll i=0;i<n;i++){
update(1,1,c,L[i],R[i],1);
}
for(ll i=1;i<c;i++){
A[i]=find(1,1,c,i,i);
if(A[i]==k+1)
B.push_back(i);
if(A[i]==k)
C.push_back(i);
//A[i]=0;
}
ll ans=INT_MIN;
ll x,y;
for(ll i=0;i<n;i++){
x=lower_bound(B.begin(),B.end(),L[i])-B.begin();
y=lower_bound(B.begin(),B.end(),R[i])-B.begin();;
if(y==B.size() || B[y]!=R[i])
y--;
a=y-x+1;
x=lower_bound(C.begin(),C.end(),L[i])-C.begin();;
y=lower_bound(C.begin(),C.end(),R[i])-C.begin();;
if(y==C.size() ||C[y]!=R[i])
y--;
a+=C.size();
a-=y-x+1;
ans=max(ans,a);
}
/* for(ll i=0;i<4*c;i++){
U[i]=T[i]=0;
}
*//* for(ll i=1;i<c;i++)
cout<<A[i]<<" "<<i<<endl;
*/
cout<<ans<<endl;
}
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCiNkZWZpbmUgbGwgbG9uZyBsb25nCgpsbCBUWzQwMDA1NV09ezB9LFVbNDAwMDU1XT17MH0sQVsxMDAwMjBdPXswfTsKdm9pZCBidWlsZChsbCBub2RlLGxsIHMsbGwgZSl7CglpZihzPT1lKQoJCVRbbm9kZV09MDsKCWVsc2V7CgkJbGwgbWlkPShzK2UpPj4xOwoJCWJ1aWxkKDIqbm9kZSxzLG1pZCk7CgkJYnVpbGQoMipub2RlKzEsbWlkKzEsZSk7Cgl9Cn0Kdm9pZCB1cGRhdGUobGwgbm9kZSxsbCBzLGxsIGUsbGwgeCxsbCB5LGxsIHZhbCl7CglpZihVW25vZGVdIT0wKXsKCQlUW25vZGVdKz0oZS1zKzEpKlVbbm9kZV07CgkJaWYocyE9ZSl7CgkJCVVbMipub2RlXSs9VVtub2RlXTsKCQkJVVsyKm5vZGUrMV0rPVVbbm9kZV07CgkJfQoJCVVbbm9kZV09MDsKCX0KCglpZihzPmUgfHwgcz55IHx8IGU8eCkKCQlyZXR1cm47CglpZihzPj14ICYmIGU8PXkpewoJCVRbbm9kZV0rPShlLXMrMSkqdmFsOwoJCWlmKHMhPWUpewoJCQlVWzIqbm9kZV0rPXZhbDsKCQkJVVsyKm5vZGUrMV0rPXZhbDsKCQl9CgkJcmV0dXJuIDsKCX0KCWxsIG1pZD0ocytlKT4+MTsKCXVwZGF0ZSgyKm5vZGUscyxtaWQseCx5LHZhbCk7Cgl1cGRhdGUoMipub2RlKzEsbWlkKzEsZSx4LHksdmFsKTsKCVRbbm9kZV09VFsyKm5vZGVdK1RbMipub2RlKzFdOwp9CgoKbGwgZmluZChsbCBub2RlLGxsIHMsbGwgZSxsbCB4LGxsIHkpewoJaWYoeD5lIHx8IHk8cykKCQlyZXR1cm4gMDsKCWlmKFVbbm9kZV0hPTApewoJCVRbbm9kZV0rPShlLXMrMSkqVVtub2RlXTsKCQlpZihzIT1lKXsKCQkJVVsyKm5vZGVdKz1VW25vZGVdOwoJCQlVWzIqbm9kZSsxXSs9VVtub2RlXTsKCQl9CgkJVVtub2RlXT0wOwoJfQoJaWYocz49eCAmJiBlPD15KXsKCSAgICBsbCB4PVRbbm9kZV07CgkgICAgVFtub2RlXT1VW25vZGVdPTA7CgkgICAgcmV0dXJuIHg7Cgl9CglsbCBtaWQ9KHMrZSk+PjE7CglsbCBwMT1maW5kKDIqbm9kZSxzLG1pZCx4LHkpOwoJbGwgcDI9ZmluZCgyKm5vZGUrMSxtaWQrMSxlLHgseSk7CglUW25vZGVdPTA7CglyZXR1cm4gcDErcDI7Cn0KCmludCBtYWluKCl7CglsbCB0OwoJY2luPj50OwoJd2hpbGUodC0tKXsKCQlsbCBuLGssYSxiOwoJCWNpbj4+bj4+azsKCQlsbCBjPUlOVF9NSU47CgkJbGwgUltuKzFdLExbbisxXTsKLyoKCQltZW1zZXQoQSwwLHNpemVvZihBKSk7CgkJbWVtc2V0KFQsMCxzaXplb2YoVCkpOwoJCW1lbXNldChVLDAsc2l6ZW9mKFUpKTsqLwoJCXZlY3RvcjxsbD4gQixDOwoKCQlmb3IobGwgaT0wO2k8bjtpKyspewoJCQljaW4+PkxbaV0+PlJbaV07CgkgICAgICAgIGM9bWF4KGMsUltpXSszKTsKCQl9CgkvLwlidWlsZCgxLDEsYyk7CgkJZm9yKGxsIGk9MDtpPG47aSsrKXsKCQkJdXBkYXRlKDEsMSxjLExbaV0sUltpXSwxKTsKCQl9CgoJCWZvcihsbCBpPTE7aTxjO2krKyl7CgkJCUFbaV09ZmluZCgxLDEsYyxpLGkpOwoJCQlpZihBW2ldPT1rKzEpCgkJCQlCLnB1c2hfYmFjayhpKTsKCgkJCWlmKEFbaV09PWspCgkJCQlDLnB1c2hfYmFjayhpKTsKLy9BW2ldPTA7CgkJfQoJCQoJCWxsIGFucz1JTlRfTUlOOwoJCWxsIHgseTsKCQlmb3IobGwgaT0wO2k8bjtpKyspewoJCQl4PWxvd2VyX2JvdW5kKEIuYmVnaW4oKSxCLmVuZCgpLExbaV0pLUIuYmVnaW4oKTsKCQkJeT1sb3dlcl9ib3VuZChCLmJlZ2luKCksQi5lbmQoKSxSW2ldKS1CLmJlZ2luKCk7OwoJCQlpZih5PT1CLnNpemUoKSB8fCBCW3ldIT1SW2ldKQoJCQkJeS0tOwoJCQlhPXkteCsxOwoJCQl4PWxvd2VyX2JvdW5kKEMuYmVnaW4oKSxDLmVuZCgpLExbaV0pLUMuYmVnaW4oKTs7CgkJCXk9bG93ZXJfYm91bmQoQy5iZWdpbigpLEMuZW5kKCksUltpXSktQy5iZWdpbigpOzsKCQkJaWYoeT09Qy5zaXplKCkgfHxDW3ldIT1SW2ldKQoJCQkJeS0tOwoJCQlhKz1DLnNpemUoKTsKCQkJYS09eS14KzE7CgkJCWFucz1tYXgoYW5zLGEpOwoJCX0KCgkvKglmb3IobGwgaT0wO2k8NCpjO2krKyl7CgkJICAgIFVbaV09VFtpXT0wOwoJCX0KCSovLyoJZm9yKGxsIGk9MTtpPGM7aSsrKSAKCQkJY291dDw8QVtpXTw8IiAiPDxpPDxlbmRsOwoqLwoJCWNvdXQ8PGFuczw8ZW5kbDsKCX0JCn0KCg==