#include<cstdio>

#include<algorithm>

using namespace std;

const int N=100010,M=1800000;

int C,n,k,i,j,ans,bit[N],b[N],vis[N];

struct P{int x,y,c;}a[N];

inline bool cmpc(P a,P b){return a.c==b.c?a.x<b.x:a.c<b.c;}

inline bool cmpy(P a,P b){return a.y<b.y;}

inline void up(int x){if(ans<x)ans=x;}

inline int lower(int x){

  int l=1,r=n,t,mid;

  while(l<=r)if(b[mid=(l+r)>>1]<=x)l=(t=mid)+1;else r=mid-1;

  return t;

}

inline void add(int x){for(;x<=n;x+=x&-x)bit[x]++;}

inline int ask(int x){int t=0;for(;x;x-=x&-x)t+=bit[x];return t;}

inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}

int T[N],vl[M],vr[M],l[M],r[M],tot,pre,nxt;

void ins(int&x,int a,int b,int c){

  if(!x)x=++tot;

  if(a==b){vl[x]=vr[x]=a;return;}

  int mid=(a+b)>>1;

  if(c<=mid)ins(l[x],a,mid,c);else ins(r[x],mid+1,b,c);

  vl[x]=vl[l[x]]?vl[l[x]]:vl[r[x]];

  vr[x]=vr[r[x]]?vr[r[x]]:vr[l[x]];

}

void getl(int x,int a,int b,int c){

  if(!x||nxt)return;

  if(c<=a){nxt=vl[x];return;}

  int mid=(a+b)>>1;

  if(c<=mid)getl(l[x],a,mid,c);

  getl(r[x],mid+1,b,c);

}

void getr(int x,int a,int b,int d){

  if(!x||pre)return;

  if(b<=d){pre=vr[x];return;}

  int mid=(a+b)>>1;

  if(d>mid)getr(r[x],mid+1,b,d);

  getr(l[x],a,mid,d);

}

int main(){

  for(read(C);C--;printf("%d\n",ans)){

    read(n),read(k);

    for(i=1;i<=k;i++)vis[i]=0;

    for(ans=0,i=1;i<=n;i++)read(a[i].x),read(a[i].y),read(a[i].c),b[i]=a[i].x,vis[a[i].c]=1;

    for(sort(b+1,b+n+1),sort(a+1,a+n+1,cmpy),i=1;i<=n;i++)a[i].x=lower(a[i].x);

    for(i=1;i<=n;i++)bit[i]=0;

    for(i=1;i<=k;i++)if(!vis[i]){ans=n;break;}

    if(ans)continue;

    for(i=1;i<=tot;i++)vl[i]=vr[i]=l[i]=r[i]=0;tot=0;

    for(i=1;i<=k;i++)T[i]=0,ins(T[i],0,n+1,0),ins(T[i],0,n+1,n+1);

    for(i=1;i<=n;i=j){

      for(j=i;j<=n&&a[j].y==a[i].y;j++){

        pre=nxt=0,getl(T[a[j].c],0,n+1,a[j].x),getr(T[a[j].c],0,n+1,a[j].x);

        up(ask(nxt-1)-ask(pre));

      }

      for(j=i;j<=n&&a[j].y==a[i].y;j++)ins(T[a[j].c],0,n+1,a[j].x),add(a[j].x);

    }

    for(i=1;i<=n;i++)bit[i]=0;

    for(i=1;i<=tot;i++)vl[i]=vr[i]=l[i]=r[i]=0;tot=0;

    for(i=1;i<=k;i++)T[i]=0,ins(T[i],0,n+1,0),ins(T[i],0,n+1,n+1);

    for(i=n;i;i=j){

      for(j=i;j&&a[j].y==a[i].y;j--){

        pre=nxt=0,getl(T[a[j].c],0,n+1,a[j].x),getr(T[a[j].c],0,n+1,a[j].x);

        up(ask(nxt-1)-ask(pre));

      }

      for(j=i;j&&a[j].y==a[i].y;j--)ins(T[a[j].c],0,n+1,a[j].x),add(a[j].x);

    }

    for(sort(a+1,a+n+1,cmpc),i=1;i<=n;i++)bit[i]=0;

    for(i=1;i<=n;i++)bit[a[i].x]++;

    for(i=2;i<=n;i++)bit[i]+=bit[i-1];

    for(i=1;i<n;i++)if(a[i].c==a[i+1].c)up(bit[a[i+1].x-1]-bit[a[i].x]);

    else up(max(n-bit[a[i].x],bit[a[i+1].x-1]));

    up(max(bit[a[1].x-1],n-bit[a[n].x]));

  }

  return 0;

}