/*����ϵͳż������BUG��ƴ��ȫ�����10min����սʤ*/
#include<bits/stdc++.h>
#define MAXN 200005

using namespace std;

struct S{
	int l1, l2, r1, r2;
}s[MAXN];
struct S1{
	int a, b;
}s1[MAXN];

int top = 0;

bool cmp1(S1 a, S1 b){
	return a.b < b.b;
}
bool cmp2(S a, S b){
	if(a.r2 != b.r2) return a.r2 < b.r2;
	return a.l2 < b.l2;
}

int c, T;
int n;
int nums[MAXN<<1];

bool vis[MAXN];
int tot, ans;
void work2(int pos){
	if(pos == n+1){
		sort(s1+1, s1+1+n, cmp1);
		int sum = 0, mid = (tot+1)/2;
		for(int i = 1; i <= n; i++){
			sum += s1[i].a;
			if(sum >= mid){
				if(!vis[s1[i].b]){
					ans++;
					vis[s1[i].b] = 1;
				}
				break;
			}
		}
		return;
	}
	
	for(int i = s[pos].l1; i <= s[pos].r1; i++){
		s1[pos].a = i; tot += i;
		for(int j = s[pos].l2; j <= s[pos].r2; j++){
			s1[pos].b = i;
			work2(pos+1);
		}
		tot -= i;
	}
}

void work1(){
	int tot = 0, mid = 0, ans = 0;
	sort(s+1, s+1+n, cmp2);
	for(int i = 1; i <= n; i++) tot += s[i].l1;
	mid = (tot+1) / 2;
//	cout << mid <<"\n";
	for(int i = 1; i <= n; i++) nums[ s[i].l2 ] += s[i].l1;
	
	int now = 0, sum = 0, j = 1;
	for(int i = 1; i <= top; i++){
//		cout << top << " ";
		now += nums[i];//now:��ǰ�ж�������ֵĸ��� 
		while(j <= n && s[j].r2 < i){//sum:ʼ��С�ڵ�ǰ������� 
			now -= s[j].l1;
			sum += s[j].l1;
			j++;
		}
		if(!now) continue;
//		cout << i << " " << sum << " " << now << "\n";
		if(sum >= mid) break;//ʼ�ղ��ܴﵽmidλ��
		if(sum < mid && sum + now >= mid) ans++;//���Դﵽmid 
	}
	
	cout << ans << "\n";
}
//5qB9c88b
void init(){
	top = 0; ans = 0; tot = 0;
	memset(nums, 0, sizeof nums);
}

int main(){
	ios::sync_with_stdio(0);
	freopen("lucky.in", "r", stdin);
	freopen("lucky.out", "w", stdout);
	
	cin >> c >> T;
	while(T--){
		init();
		cin >> n;
		for(int i = 1; i <= n; i ++){
			cin >> s[i].l1 >> s[i].r1 >> s[i].l2 >> s[i].r2;
			top = max(top, s[i].r2);
		}
		
		if(c == 2){
			memset(vis, 0, sizeof vis);
			work2(1);
			cout << ans << "\n"; 
		}
		else work1();
	}
	
	return 0;
}