#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

typedef struct _WALLS
{
	int nStartx;
	int nStarty;
	
	int nEndx;
	int nEndy;
}WALLS;


void Zeros(int **a,int nRow,int nColumn)
{
	int n,m;
	for(n=0;n<=nRow;n++)
	{
		for(m=0;m<=nColumn;m++)
		{
			a[n][m]=0;
		}
	}
}

int PointInWhichWalls(WALLS *pWalls,int nWalls ,int n,int m)
{
	int i;
	for(i=0;i<nWalls;i++)
	{
		if( pWalls[i].nStartx<=m && m<=pWalls[i].nEndx && n==pWalls[i].nStarty)
			return i;
	}
	return 0;
}


int GetBadWallIndex(int *pnBadWall,int nWalls)
{
	int max=0;
	int i;
	for(i=0;i<nWalls;i++)
	{
		if (pnBadWall[i]>max)
		{
			max=pnBadWall[i];
		}
	}
	return max;
}


void main()
{

	int i,j;
	int n,m;

	int **a;
	int k;
	int nTime;
	int nWalls;
	WALLS *pWalls;
	int *pnBadWall;

	int nMaxColumn=0;
	int nMaxRow=0;

	int nColumnCount=0;
	int nDesWall;
	int flag=0;

	int nResult=0;

	scanf("%d",&nTime);

	for(i=0;i<nTime;i++)
	{
		scanf("%d %d",&nWalls,&k);

		pWalls=(WALLS *)malloc(sizeof(WALLS)*nWalls);
		pnBadWall=(int *)malloc(sizeof(int)*nWalls);

		for(j=0;j<nWalls;j++)
		{
			scanf("%d %d %d %d",
				&pWalls[j].nStartx,
				&pWalls[j].nStarty,
				&pWalls[j].nEndx,
				&pWalls[j].nEndy);

			if(pWalls[j].nEndx>nMaxColumn)
				nMaxColumn=pWalls[j].nEndx;

			if(pWalls[j].nStarty>nMaxRow)
				nMaxRow=pWalls[j].nStarty;

			pnBadWall[j]=0;

		}

		a=(int **)malloc(sizeof(int *)*(nMaxRow+1));
		for(j=0;j<=nMaxRow;j++)
		{
			a[j]=(int *)malloc(sizeof(int)*(nMaxColumn+1));
		}
		Zeros(a, nMaxRow, nMaxColumn);

		for(j=0;j<nWalls;j++)
		{
			for(m=pWalls[j].nStartx;m<=pWalls[j].nEndx;m++)
			{
				a[pWalls[j].nStarty][m]=1;
			}
		}

		do 
		{			
			flag=0;
			for(m=0;m<=nMaxColumn;m++)
			{
				nColumnCount=0;
				for(n=0;n<=nMaxRow;n++)
				{
					if(a[n][m]==1)
						nColumnCount++;
				}

				if(nColumnCount>k)
				{
					flag=1;

					for(n=0;n<=nMaxRow;n++)
					{
						if(a[n][m]==1)
						{
							nDesWall=PointInWhichWalls(pWalls,nWalls,n,m);
							pnBadWall[nDesWall]++;
						}
					}				
				}
				else if(flag!=1)
				{
					flag=0;
				}
			}

			if(flag==1)
			{
				nDesWall=GetBadWallIndex(pnBadWall,nWalls);

				for(m=pWalls[nDesWall].nStartx; pWalls[nDesWall].nEndx; m++)
                {
					a[ pWalls[nDesWall].nStarty ][m]=0;
				}

				nResult++;
			}		
		
		} while(flag);

		printf("%d\n",nResult);

		nResult=0;
		Zeros(a, nMaxRow, nMaxColumn);
	}
	
	free(pWalls);
	free(pnBadWall);
	
	for(j=0;j<=nMaxRow;j++)
	{
		free(a[j]);
	}
	free(a);
}