#include<iostream>

 #include<cstring>

 using namespace std;

 int t,n,k,x,y,x1,y2,max_x,max_y,sum_s=;

 //(x,y) (x1,y1)墙的两个端点，所有墙最大列坐标max_x，最大行坐标max_y，最少拆除墙面数为sum_s

 int map[][];

 int main()

 {

     scanf("%d",&t);//测试用例数

     while(t--)

     {

         memset(map,,sizeof(map));

         max_x=;

         max_y=;

         sum_s=;

         scanf("%d %d",&n,&k);

         for(int i=;i<=n;i++)

         {

             scanf("%d %d %d %d",&x,&y,&x1,&y2);//两个端点坐标

             if(x>max_x)

                 max_x=x;

             if(x1>max_x)

                 max_x=x1;

             if(y>max_y)

                 max_y=y;//y=y2，所以只要一句

             if(x<x1)//标记第i面墙

             {

                 for(int j=x;j<=x1;j++)

                     map[j][y]=i;

             }

             else

             {

                 for(int j=x1;j<=x;j++)

                     map[j][y]=i;

             }

         }    

         for(int i=;i<=max_x;i++)//从左到右扫描每一列

         {

             int tem=;//统计第i列中墙的格子数

             for(int j=;j<=max_y;j++)

             {

                 if(map[i][j]>)

                     tem++;

             }

             int offset=tem-k;//墙多，则要拆offset面

             if(offset>)

             {

                 sum_s+=offset;

                 while(offset--)

                 {

                     int max_s=,max_bh;//最多的格子数,行数

                     for(int k=;k<=max_y;k++)//搜索第i列每个有墙的格子

                     {

                         if(map[i][k]>)//若(i,k)为有墙格，则统计k行i列右方属于同堵墙的格子数tem_s

                         {

                             int tem_s=;

                             for(int z=i+;z<=max_x;z++)

                             {

                                 if(map[z][k]==map[i][k])

                                     tem_s++;

                             }

                             if(max_s<tem_s)//该堵墙格子数最多，则记下

                             {

                                 max_s=tem_s;

                                 max_bh=k;

                             }

                          }

                     }

                     //拆除含格子数最多的墙(第max_bh行上第i列开始的max_s个格子)

                     for(int a=i;a<=i+max_s;a++)

                     {

                         map[a][max_bh]=;//拆除，不然会重复计数

                     }

                 }

             }

         }

         printf("%d\n",sum_s);//输出最少拆除墙的面数

     }

     return ;

  }