#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define ll long long
#define mod 10000007
using namespace std;
ll read()
{
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int ans;
int T,n,K;
struct data{
    int x,y,z;
    int id;
}p[100005];
int x[100005];
int disc[100005],t[100005];
int last[100005],l[100005],r[100005];
void add(int x,int val)
{
    for(;x<=n+1;x+=x&-x)
        t[x]+=val;
}
int query(int x)
{
    int ans=0;
    for(;x>0;x-=x&-x)
        ans+=t[x];
    return ans;
}
bool cmpx(data a,data b)
{
    return a.x<b.x;
}
bool cmpy(data a,data b)
{
    return a.y<b.y;
}
void update(int l,int r)
{
    if(l>r)return;
    int tmp=query(r)-query(l-1);
    ans=max(tmp,ans);
}
void solve()
{
    x[0]=0;x[n+1]=n+1;
    memset(last,0,sizeof(last));
    memset(t,0,sizeof(t));
    sort(p+1,p+n+1,cmpx); 
    for(int i=1;i<=n;i++)
        add(p[i].x,1);
    for(int i=1;i<=n;i++)
    {        
        int t=p[i].id,L=last[p[i].z];
        l[t]=L;r[t]=n+1;
        if(L)r[L]=t;
        update(x[L]+1,x[t]-1);
        last[p[i].z]=t;
    }
    for(int i=1;i<=K;i++)
        update(x[last[i]]+1,n+1);
    sort(p+1,p+n+1,cmpy);
    for(int i=1,j=1;i<=n;i++)
    {
        int t=p[i].id;
        while(j<=n&&p[j].y==p[i].y)
        {
            add(p[j].x,-1);
            j++;
        }
        l[r[t]]=l[t];r[l[t]]=r[t];
        update(x[l[t]]+1,x[r[t]]-1);
    }
}
int main()
{
	freopen("candy.in","r",stdin);
	freopen("candy.out","w",stdout);
    T=read();
    while(T--)
    {
        ans=0;
        n=read();K=read();
        for(int i=1;i<=n;i++)
        {
            p[i].x=read(),p[i].y=read(),p[i].z=read();
            p[i].id=i;
        }
        for(int i=1;i<=n;i++)
            disc[i]=p[i].x;
        sort(disc+1,disc+n+1);
        for(int i=1;i<=n;i++)
        {
            p[i].x=lower_bound(disc+1,disc+n+1,p[i].x)-disc;
            x[i]=p[i].x;
        }
        solve();
        for(int i=1;i<=n;i++)
            p[i].y=-p[i].y;
        solve();
        printf("%d\n",ans);
    }
    return 0;
}