#include<cstdio>
#include<algorithm>
using namespace std;

int n;

int const N=2e5;

struct _{
    int left, right;
} cnt[N], num[N];

bool check_left(int val){
	long long less=0, more=0;
	for(int i=0; i<n; i++){
		if(val < num[i].left) more += cnt[i].left;
		else less += cnt[i].right;
	}
	
	return less>=(less+more+1)/2;
}

bool check_right(int val){
	long long less=0, more=0;
	for(int i=0; i<n; i++){
		if(val > num[i].right) less += cnt[i].left;
		else more += cnt[i].right;
	}
	
	return less<(less+more+1)/2;
}

bool cmp(_ a, _ b){
	return a.left<b.left;
}

void fuction(){
    scanf("%d", &n);

	int minn=1e9, maxn=0; 
    for(int i=0; i<n; i++){
		scanf("%d%d%d%d", &cnt[i].left, &cnt[i].right, &num[i].left, &num[i].right);
		
		minn = min(minn, num[i].left);
		maxn = max(maxn, num[i].right);
	}
	
	_ left, right;
	left.left = right.left = minn, left.right = right.right = maxn;

	while(left.left <= left.right){
		int mid=(left.left+left.right)/2;
		
		if(check_left(mid)) left.right = --mid; 
		else left.left = ++mid;
	}
	
	while(right.left <= right.right){
		int mid=(right.left+right.right)/2;
		
		if(check_right(mid)) right.left = ++mid;
		else right.right = --mid;
	}
	
	sort(num, num+n, cmp);
	
	int sum=0;
	
	int last=--left.left;
	for(int i=0; i<n; i++){
		num[i].left = max(--num[i].left, last);
		num[i].right = min(num[i].right, right.right);
		
		if(num[i].right > last){
			sum += num[i].right-num[i].left;
			
			last = num[i].right;
		}
	}
	
	printf("%d\n", sum);
	
    return ;
}

int main(){
	freopen("lucky.in", "r", stdin);
	freopen("lucky.out", "w", stdout);
	
    int T;
    scanf("%*d%d", &T);

    while(T--) fuction();
    
    fclose(stdin);
    fclose(stdout);

    return 0;
}