#include <iostream.h>


struct wall{
	int top;//某列墙的数量
	int walid[100];//墙的序号
};

int times[100];

int max()
{
	int maxs=times[0],id=0;
	for(int i=1;i<100;i++)
		if(times[i]>maxs)
		{
			maxs=times[i];
			id=i;
		}
	return id;
}

int main(int argc, char* argv[])
{
	int t,n,k,*x1,*y1,*x2,*y2,i,j,stack[101],st,move,sign;
	wall wall[101];
	cin>>t;
	while(t--)
	{
		cin>>n>>k;
		x1=new int[n];
		y1=new int[n];
		x2=new int[n];
		y2=new int[n];
		i=0;
		for(j=0;j<101;j++)
			wall[j].top=0;
		while(i<n)
		{
			cin>>x1[i]>>y1[i]>>x2[i]>>y2[i];
			if(x1[i]>=x2[i])
				for(j=x2[i];j<=x1[i];j++)
					wall[j].walid[wall[j].top++]=i;
			else
				for(j=x1[i];j<=x2[i];j++)
					wall[j].walid[wall[j].top++]=i;
			i++;
		}
		move=0;
		while(1)
		{
			st=0;//不能通过的列的数量
			for(i=0;i<101;i++)
				if(wall[i].top>k)
					stack[st++]=i;//不能通过的列的序号
			if(st==0)
			{
				cout<<move<<endl;
				break;
			}
			for(j=0;j<100;j++)
				times[j]=0;
			for(i=0;i<st;i++)
				for(j=0;j<wall[stack[i]].top;j++)
				{
					sign=wall[stack[i]].walid[j];
					times[sign]++;
				}
			int m=max();
			for(i=0;i<st;i++)
				for(j=0;j<wall[stack[i]].top;j++)
					if(wall[stack[i]].walid[j]==m)
					{
						wall[stack[i]].walid[j]=wall[stack[i]].walid[--wall[stack[i]].top];
						break;
					}
			move++;
		}
		
		
		
	}
	return 1;
}