#include<bits/stdc++.h>
#define N 11451
using namespace std;
int read()
{
	int f=1,reans=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		reans=reans*10+ch-'0';
		ch=getchar();
	}
	return f*reans;
} 
struct node{
	int l1,r1,l2,r2;
}qv[N];
struct node2{
int da,val;	
}qv2[N];
bool cmp(node ff,node ss){
	return ff.l2<ss.l2;
}
bool cmp2(node2 ff,node2 ss)
{
	return ff.val<ss.val;
}
bool dp[N][10][2000];
int sum[N][10][2000];
int c,T;
int n;
int summ[N][10];
bool vis[N];
int main()
{
	freopen("lucky.in","r",stdin);
	freopen("lucky.out","w",stdout);
	//dp[i][j]������iСΪȡ��j������li2��, dp[i][j]=||{dp[i-a[j]-1][t]}t<=j,r<=a[j]<=l 
	c=read(),T=read();
	while(T--)
	{
		
		int ans=0;
		n=read();
		int ss=0;
		for(int i=1;i<=n;i++)
		{
			qv[i].l1=read(),qv[i].r1=read();
			ss+=qv[i].l1;qv2[i].da=qv[i].l1;
			qv[i].l2=read(),qv[i].r2=read();qv2[i].val=qv[i].r2;
		} 
		for(int i=1;i<=ss;i++) vis[i]=0;
		int kk=(ss+1)/2;
		//cout<<kk<<endl;
		sort(qv+1,qv+1+n,cmp);
		sort(qv2+1,qv2+1+n,cmp2);
		for(int g=1;g<=n;g++)
		{
			summ[n+1][g]=0;
			for(int i=n;i>=1;i--)
			{
				if(i==g) summ[i][g]=summ[i+1][g];
				else summ[i][g]=summ[i+1][g]+qv2[i].da;
			}
		}
			
		for(int i=0;i<=n;i++)for(int g=1;g<=n;g++)dp[0][g][i]=1,sum[0][g][i]=1;
		for(int i=1;i<=ss;i++)
		{
		//	cout<<endl;
			for(int g=1;g<=n;g++)
			{
				int su=1;
				for(int j=1;j<=n;j++)
			{
				while(su+1<=n&&qv2[su+1].val<qv[j].l1) su++;
				if(j==g) continue;
				int su2=1;
				for(int k=qv[j].l1;k<=min(i,qv[j].r1);k++)
				{
					while(su2+1<=n&&qv2[su2+1].val<k) {
						su2++;
					}
					if(i-k<0) continue;
					dp[i][g][j]=dp[i][g][j]||sum[i-k][g][j-1];
					if(dp[i][g][j]) break;
				}
				if(summ[su][g]<ss-i) dp[i][g][j]=0;
				sum[i][g][j]=sum[i][g][j-1]||dp[i][g][j];
				//cout<<dp[i][j]<<" ";
				
			}//cout<<endl;
			}
			
		}
		for(int i=1;i<=n;i++)
		{
			int su=1;
			
			for(int j=qv[i].l2;j<=qv[i].r2;j++)
			{
				int flag=0;
				while(su+1<=n&&qv2[su+1].val<j) su++;

				for(int k=qv[i].l1;k<=qv[i].r1;k++){
					for(int q=1;q<=k;q++) {
						if(ss-summ[su+1][i]<kk-q) continue;
						if(sum[kk-q][i][su]) {
						flag=1;break;
					}
					}
					if(flag) break;
				}
				if(flag&&vis[j]==0) {
					ans++,vis[j]=1;
					//cout<<j<<endl;
				}
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}
/*
0 1
4
3 3 4 4
1 1 1 4
2 2 1 1
3 3 3 4
*/