#include <bits/stdc++.h>
#define x first
#define y second
#define piii pair<pair<int,int> ,int>
#define pii pair<int,int>


using namespace std;
ifstream in("cutii.in");
ofstream out("cutii.out");
const int NM = 3505;
int t,n;
int aib[NM][NM];
char test[NM][NM];

int find_max(int i,int j)
{
    int maxx=0;
    for(int pi=i; pi>0; pi-=(pi)&(-pi))
        for(int pj=j; pj>0; pj-=(pj)&(-pj))
        {
            if(test[pi][pj]!=t)aib[pi][pj]=0;
            maxx=max(maxx,aib[pi][pj]);
            test[pi][pj]=t;
        }
    return maxx;
}

void update(int i,int j)
{
    for(int pi=i; pi<=n; pi+=(pi)&(-pi))
        for(int pj=j; pj<=n; pj+=(pj)&(-pj))
        {
            if(test[pi][pj]!=t)aib[pi][pj]=0;
            aib[pi][pj]=max(aib[pi][pj],aib[i][j]);
            test[pi][pj]=t;
        }
}

piii a[NM];

int main()
{
    in>>n>>t;

    while(t--)
    {
        for(int i=1; i<=n; ++i)in>>a[i].x.x>>a[i].x.y>>a[i].y;
        int sol=0;
        for(int i=1; i<=n; ++i)
        {

            int px,py;
            px=a[a[i].y].x.x;
            py=a[a[i].y].x.y;

            aib[px][py]=find_max(px-1,py-1)+1;
            test[px][py]=t;
            update(px,py);
            sol=max(sol,aib[px][py]);

        }
        out<<sol<<'\n';
    }

    return 0;
}