#include<iostream>
#include<Algorithm>
#include<memory>
using namespace std;
int t, n, k, maxx, maxy, ans;
int chart[102][102][2];

bool cmp( int a, int b ) 
{   return a > b; }  

void init()
{
	int i,j,x1,y,x2;
	scanf("%i %i",&n,&k);
	for (i=1;i<=n;i++)
	{
		scanf("%i %i %i %i",&x1,&y,&x2,&y);		
		if (x2 < x1) swap(x1,x2);
		if (maxx < x2) maxx=x2;
		if (maxy < y) maxy=y;		
		for (j=x1;j<=x2;j++)
		{
			chart[j][y][1]=1;
			chart[j][y][0]=x2-j;
		}
	}	
}

void work()
{
	int i,j,l,temp,block;
	int c[102];
	for (i=0;i<=maxx;i++)
	{
		block=0;
		for (j=0;j<=maxy;j++)
		{
			if (chart[i][j][1]==1) block++;
			c[j]=chart[i][j][0];
		}		
		sort(c,c+maxy+1,cmp);

		if (block>k)
		for (j=0;j<block-k;j++)
		{
			for (l=0;l<=maxy;l++)
				if (chart[i][l][0]==c[j])
					for (temp=i;temp<=i+c[j];temp++)
					{
						chart[temp][l][0]=0;
						chart[temp][l][1]=0;
					}
			ans++;
		}

	}
}

int main()
{
	scanf("%i",&t);
	while (t>0)
	{
		t--; maxx=0; maxy=0; ans=0;
		memset(chart,0,sizeof(chart));
		init();
		work();
		cout<<ans<<endl;
	}
	return 0;
}