#include <iostream>
using namespace std ;
int main(){
	int t , grid[100][100] , n , k , sta_x , sta_y , end_x , end_y ;
	cin >> t ;
	while( t -- )
	{
		cin >> n >> k ; 
		memset( grid , 0 , sizeof( grid ) ) ;
		int max_y = 0 , max_x = 0 ;
		for( int i = 0 ; i < n ; i ++ )
		{
			cin >>  sta_y >> sta_x >> end_y >> end_x ;
			if( end_y > max_y )
				max_y = end_y ;
			if( sta_y > max_y )
				max_y = sta_y ;
			if( sta_x > max_x )
				max_x = sta_x ;
			if( sta_y > end_y )                //处理 sta_y > end_y 的情况
				swap( sta_y , end_y ) ;
			for( int j = sta_y ; j <= end_y ; j ++ )
				grid[ sta_x ][j] = 1 ;
		}
		int max = max_y ;
		if( max_x > max_y )
			max = max_x ;
		int num = 0 , k_sum ;
		for( int j2 = 0 ; j2  <= max ; j2 ++ )
		{
			k_sum = 0 ;
			for( int i1 = 0 ; i1 <= max ; i1 ++ )
				if( grid[i1][j2] == 1 )
					k_sum ++ ;
			if( k_sum > k )
			{
				for( int ii = 0 ; ii < k_sum - k ; ii ++ )   //拆墙的个数 k_sum - k ;
				{
					max_x = max_y = - 1 ;
					for( int i2 = 0 ; i2 <= max ; i2 ++ )      //寻找列数在最右边的墙并拆掉
						if( grid[i2][j2] == 1 )
						{
							for( int j3 = j2 ; ; j3 ++ )       //横向扫描墙
								if( grid[i2][j3] == 0 )
								{
									if( j3 > max_y )
									{
										max_y = j3 - 1 ;
										max_x = i2 ;
									}
									break ;
								}
						}
					for( int j4 = max_y ; j4 >= 0 ; j4 -- )  //拆找到的最右边的墙
						if( grid[ max_x ][j4] == 1 )
							grid[ max_x ][j4] = 0 ;
						else if( grid[ max_x ][j4] == 0 )
							break ;
					num ++ ;
				}
			}
		}
		cout << num << endl ;
	}
	return 0 ;
}