#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define i128 __int128
char buf[1<<21],*rp1=buf,*rp2=buf;
#define getchar() (rp1==rp2&&(rp2=(rp1=buf)+fread(buf,1,1<<21,stdin),rp1==rp2)?EOF:*rp1++)
inline i64 rd()
{
	i64 num=0;char ch=getchar();bool op=0;
	for(;!isdigit(ch);ch=getchar())if(ch=='-')op=1;
	for(;isdigit(ch);ch=getchar())num=num*10+(ch-'0');
	return op?-num:num;
}

inline void Max(int &x,int v){if(x<v)x=v;}
template<typename T>
inline void operator += (vector<T>&A,const T&v){A.emplace_back(v);}

const int N=3e5+10,M=1505;
#define pii pair<int,int>
#define fi first
#define se second

int n,m,w=0;
pii a[M][M];
int Sum[N];
struct P{int l,r,v;};
vector<P> A[M],B[M];

map<int,int> s[N];

int cnt=0,Ans=0;

inline void upd(pii &res,int x)
{
	if(res.fi!=0)
		res=pii(-1,-1);
	else if(res.se!=0)
		res.fi=x;
	else
		res.se=x;
}
struct Seg
{
	#define ls (p<<1)
	#define rs (p<<1|1)
	#define lson l,mid,p<<1
	#define rson mid+1,r,p<<1|1
	#define dmid int mid=(l+r)>>1
	
	#define root 1,m,1
	
	int tag[1<<12|3];
	bitset<N> t[1<<12|3];
	vector<int> s[1<<12|3];
	
	inline void reset(int p)
	{
		vector<int> st;
		while(!s[p].empty())
		{
			int x=s[p].back();s[p].pop_back();
			if(t[p][x])st+=x;
		}
		s[p].swap(st);
	}
	inline void ins(int L,int R,int v,int l,int r,int p)
	{
		if(L<=l&&r<=R){t[p][v]=1,tag[p]++,s[p]+=v;return;}
		dmid;if(L<=mid)ins(L,R,v,lson);if(mid<R)ins(L,R,v,rson);
	}
	inline void del(int L,int R,int v,int l,int r,int p)
	{
		if(L<=l&&r<=R){t[p][v]=0,tag[p]--;return;}
		dmid;if(L<=mid)del(L,R,v,lson);if(mid<R)del(L,R,v,rson);
	}
	inline void mkRow(int i,pii res,int l,int r,int p)
	{
		if(res.fi!=-1)
		{
			if(tag[p]<=2)
			{
				reset(p);
				for(int x:s[p])upd(res,x);	 
			}
			else res=pii(-1,-1);
		}
		if(l==r){a[i][l]=res;return;}
		dmid;mkRow(i,res,lson),mkRow(i,res,rson);
	}
	inline void build(int l,int r,int p)
	{
		tag[p]=0;vector<int>().swap(s[p]);
		if(l==r)return;dmid;build(lson),build(rson);
	}
};
Seg t;

inline void work()
{
	n=rd(),m=rd(),w=0;cnt=0,Ans=0;
	for(int i=0;i<=m+1;i++)vector<P>().swap(A[i]),vector<P>().swap(B[i]);
	
	t.build(root);
	for(int i=1;i<=n;i++)
	{
		map<int,int>().swap(s[i]);
		int x0=rd(),x1=rd(),y0=rd(),y1=rd();Sum[i]=0;
		A[x0]+=(P){y0,y1,i};B[x1+1]+=(P){y0,y1,i};
	}
	
	t.build(root);
	for(int i=1;i<=m;i++)
	{
		for(P p:A[i])t.ins(p.l,p.r,p.v,root);
		for(P p:B[i])t.del(p.l,p.r,p.v,root);
		t.mkRow(i,pii(0,0),root);
	}
	for(P p:B[m+1])t.del(p.l,p.r,p.v,root);
	
	for(int i=1;i<=m;i++)
		for(int j=1;j<=m;j++)
		{
			if(a[i][j].fi>a[i][j].se)swap(a[i][j].fi,a[i][j].se);
			if(a[i][j].se==0)cnt++;
			else if(a[i][j].fi==0)Sum[a[i][j].se]++;
		}
	for(int i=1;i<=m;i++)
		for(int j=1;j<=m;j++)
			if(a[i][j].fi>0)
			{
				int x=a[i][j].fi,y=a[i][j].se;
				Max(Ans,Sum[x]+Sum[y]+(++s[x][y]));
			}
	sort(Sum+1,Sum+n+1);
	Max(Ans,Sum[n]+Sum[n-1]);
	printf("%d\n",m*m-cnt-Ans);
}
int main()
{
	for(int test=rd();test;test--)work();
	return 0;
}