#include<bits/stdc++.h>
using namespace std;
struct aaa{
	long long l,r,x,z;
}a[600000];
long long c,T,n,w,ml,mr,nl,nr,ans,l5;
bool cmp(aaa x,aaa y)
{
	return x.x<y.x;
}
int pan(long long ml,long long mr,long long nl,long long nr,long long l5)
{
	if(l5==0)
	return 0;
	long long x=(ml+l5+nl+1)/2;
	if(x<=ml)
	{
		x=(ml+l5+nr+1)/2;
		if(x<=ml)
		return 0;
		return 1;
	}
	else if(x>l5+ml)
	{
		x=(mr+l5+nl+1)/2;
		if(x>l5+mr)
		return 0;
		return 1;
	}
	return 1;
}
int main()
{
 	ios::sync_with_stdio(0);
 	cin.tie(0);cout.tie(0);
	freopen("lucky.in","r",stdin);
	freopen("lucky.out","w",stdout);
	cin>>c>>T;
	while(T--)
	{
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>a[2*i-1].l>>a[2*i-1].r>>a[2*i-1].x>>a[2*i].x;
			a[2*i-1].x--;
			a[2*i].l=a[2*i-1].l,a[2*i].r=a[2*i-1].r;
			a[2*i-1].z=0;
			a[2*i].z=1;
			nl+=a[2*i].l;nr+=a[2*i].r;
		}
		sort(a+1,a+2*n+1,cmp);
		w=a[1].x;
		for(int i=1;i<=2*n;i++)
		{
			ans+=pan(ml,mr,nl,nr,l5)*(a[i].x-w);
			w=a[i].x;
			if(a[i].z==0)
			{
				nl-=a[i].l;nr-=a[i].r;l5+=a[i].r;
			}
			else
			{
				l5-=a[i].r;ml+=a[i].l;mr+=a[i].r;
			}
		}
		cout<<ans<<"\n";
		w=ml=mr=nl=nr=ans=l5=0;
		for(int i=1;i<=2*n;i++)
		{
			a[i].l=a[i].r=a[i].x=a[i].z=0;
		}
	}
 	return 0;
}