#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define nmax 3502
typedef struct cutie
{
  int a,b,c;
}cutie;

cutie a[nmax];
int v[nmax][nmax],sum[3][nmax];
int n;

int compare(const void *x,const void *y)
{
  return (*(cutie*)x).a-(*(cutie*)y).a;
}

int max(int x,int y)
{
  int i,j,max=0;

  for (i=x;i>=1;i=sum[1][i])
	for (j=y;j>=1;j=sum[1][j])
	  if (v[i][j]>max)
		max=v[i][j];
  return max;
}

void add(int x,int y)
{
  int i,j;

  for (i=x;i<=n;i=sum[2][i])
	for (j=y;j<=n;j=sum[2][j])
	  if (v[x][y]>v[i][j])
		v[i][j]=v[x][y];
}

FILE *f,*g;
char s[25];

int main()
{
  int t,i,j,l,k,lu;

  f=fopen("cutii.in","rt");
  g=fopen("cutii.out","wt");
  fscanf(f,"%d %d\n",&n,&t);
  for (i=1;i<nmax-1;i++)
	{
	  sum[1][i]=i-(i&(i^(i-1)));
	  sum[2][i]=i+(i&(i^(i-1)));
	}
  for (l=1;l<=t;l++)
	{
	  for (i=1;i<=n;i++)
	  {
//		fscanf(f,"%d %d %d",&a[i].a,&a[i].b,&a[i].c);

		fgets(s, 20, f);

		j = 0;
		k = 0;
		a[i].a=0;
		a[i].b=0;
		a[i].c=0;

//		while (s[j] != '\n')
		lu = strlen(s);
		for (j = 0; j < lu; j++)
		  {
			if (s[j] == ' ')
			  {
				k++;
			  }
			 else
			  {
				if (k==0) a[i].a = a[i].a * 10 + (s[j] - '0');
				  else
					{
					  if (k==1)
						a[i].b = a[i].b * 10 + (s[j] - '0');
					   else
						a[i].c = a[i].c * 10 + (s[j] - '0');
					}
			  }
		  }
	  }

	  qsort(a+1,n,sizeof(cutie),compare);

	  for (i=1;i<=n;i++)
		{
		  v[a[i].b][a[i].c]=max(a[i].b-1,a[i].c-1)+1;
		  add(a[i].b,a[i].c);
		}
	  fprintf(g,"%d\n",max(n,n));
	  for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
		  v[i][j]=0;
	}
  fclose(f);
  fclose(g);
  return 0;
}