#include <stdio.h>
#include <math.h>
#include <string.h>
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#define LL long long
#define maxn 2010
#define INF 0x3f3f3f3f
#define mod 1000000007
using namespace std;

int a[maxn],b[maxn],id[maxn] ;
int  ql,qr;
short v ;
struct node
{
    int n,mid,hehe[maxn];
    short Max[maxn*4];
    void init(int n )
    {
       for(int i=1;i<=n*4;i++)
        Max[i]=0;
       for(int i=1;i<=n;i++)
        hehe[i]=0;
    }
    void insert(int L,int R,int o )
    {
        if(L==R)
        {
            Max[o]=v;
            hehe[L]=v;
            return ;
        }
        mid=(L+R)>>1 ;
        if(ql<=mid) insert(L,mid,o<<1) ;
        else insert(mid+1,R,o<<1|1) ;
        Max[o]=max(Max[o<<1],Max[o<<1|1]);
    }
    void find(int L,int R,int o)
    {
        if(ql<=L&&qr>=R)
        {
            v=max(Max[o],v) ;
            return ;
        }
        mid=(L+R)>>1 ;
        if(ql<=mid) find(L,mid,o<<1) ;
        if(qr>mid) find(mid+1,R,o<<1|1) ;
    }
}qe[1010] ;
int main()
{
    int i,xx,yy,ans ;
    int j,n,m,pre,sz;
    int T,tmp,val;
    //freopen("in.txt","r",stdin);
    cin >> T ;
    while(T--)
    {
        scanf("%d%d",&n,&m) ;
        sz=0;
        for( i = 1 ; i <= n ;i++){
            scanf("%d%d",&a[i],&b[i]) ;
            id[sz++]=a[i];
            id[sz++]=b[i];
        }
        sort(id,id+sz) ;
        sz=unique(id,id+sz)-id;
        ans=0;
        for( i = 0; i <= m;i++)
        {
            qe[i].init(sz);
        }
        for( i = 1 ; i <= n ;i++)
        {
            a[i]=lower_bound(id,id+sz,a[i])-id;
            b[i]=lower_bound(id,id+sz,b[i])-id;
            a[i]++;b[i]++;
            for( j = min(i,m); j >= 0 ;j--)
            {
                ql=1;
                qr=a[i]-1;
                v=0;
                if(ql<=qr) qe[j].find(1,sz,1) ;
                ql=a[i] ;
                v=v+1;
                tmp=v;
                if(qe[j].hehe[ql]<v)qe[j].insert(1,sz,1);
                if(j>0){
                    ql=1;
                    qr=b[i]-1;
                    v=0;
                    if(ql<=qr) qe[j-1].find(1,sz,1) ;
                    ql=b[i] ;
                    v=v+1;
                    tmp=max(tmp,(int)v);
                    if(qe[j].hehe[ql]<v)qe[j].insert(1,sz,1);
                }
                ans=max(ans,tmp);
            }
        }
        cout<<ans<<endl;
    }
    return 0 ;
}