#include<bits/stdc++.h>
using namespace std;
#define N 200010
int T,c,n,l[N],r[N],ll[N],rr[N],a[N],cnt,p,b[2*N],tot;
long long ansl,ansr,ans;
long long m;
bool mycmp(int x,int y)
{
	return ll[x]<ll[y];
}
bool check(int x)
{
	bool ok=0;
	long long cntt=0;
	for(int i=1;i<=n;i++)
	{
		if(ll[i]<=x&&x<=rr[i])ok=1,cntt+=r[i];
	}
	if(!ok)return 0;
	long long dl=0,dr=0,ul=0,ur=0;
	for(int i=1;i<=n;i++)
	{
		if(x>rr[i])dl+=l[i],dr+=r[i];
		if(x<ll[i])ul+=l[i],ur+=r[i]; 
	}	
	if(max(dl,ul)<=min(dr,ur))return 1;
	if(dr<ul)
	{
		long long dcnt=dr,ucnt=ul,dt=ucnt-dcnt;
		if(cntt>=dt)return 1;
		else return 0;
	}
	else
	{
		long long dcnt=dl,ucnt=ur,dt=dcnt-ucnt;
		if(cntt>dt)return 1;
		else return 0;
		
		
	}
}
bool cmp(int x,int y)
{
	return ll[x]<ll[y]||(ll[x]==ll[y]&&rr[x]<rr[y]);
}
int main()
{
	freopen("lucky.in","r",stdin);
	freopen("lucky.out","w",stdout);
	scanf("%d%d",&c,&T);
	while(T--)
	{
		scanf("%d",&n);
		m=0;	
		tot=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d%d%d%d",&l[i],&r[i],&ll[i],&rr[i]);
			a[i]=i;
			b[++tot]=ll[i];
			b[++tot]=rr[i];
			m+=l[i];
		}
		sort(a+1,a+1+n,mycmp);
		sort(b+1,b+1+tot);
		m=(m+1)/2;
		for(int i=1;i<=n;i++)
		{
			if(m<=l[a[i]])
			{
				p=ll[a[i]];
				break;
			}
			else m-=l[a[i]];
		}
		for(int i=1;i<=tot;i++)
		{
			if(b[i]==p)
			{
				p=i;
				break;
			}		
		}
		int L=1,R=p;
		while(L+1<R)
		{
			int mid=(L+R)/2;
			if(check(b[mid]))R=mid;
			else L=mid;
		}
		if(check(b[L]))ansl=b[L];
		else ansl=b[R];
		L=p,R=tot;
		while(L+1<R)
		{
			int mid=(L+R)/2;
			if(check(b[mid]))L=mid;
			else R=mid;
		}
		if(check(b[R]))ansr=b[R];
		else ansr=b[L];
		ans=ansr-ansl+1;
		for(int i=1;i<=n;i++)a[i]=i;
		sort(a+1,a+1+n,cmp);
		bool f=0;
		int rmax=0;
		for(int i=1;i<=n;i++)
		{
			if(rr[a[i]]<ansl)continue;
			if(ll[a[i]]>ansr)continue;
			if(!f)
			{
				rmax=rr[a[i]];
				f=1;
				continue;
			}
			if(ll[a[i]]>rmax)ans-=(ll[a[i]]-rmax-1);
			rmax=max(rr[a[i]],rmax);
			if(rmax>=ansr)break;
		}
		printf("%lld\n",ans);	
	}
	return 0;
}
/*
*/