自己测极限数据是过了的，三个暴力点都是第九组数据出现的错误

#include<bits/stdc++.h>
#define pi pair<int,int> 
#define mid (l+r)/2
#define N 100001
using namespace std;
int t,n,k,l[N],r[N],a[N],ans;
int dfs2(int s){
	if(s==n+1){
		return 1;
	}
	int z=0;
	if(a[s]>=2||a[s]==0)z|=dfs2(s+1);
	if(a[s]>0&&a[s+1]>0&&a[s+2]>0){
		a[s]--;
		a[s+1]--;
		a[s+2]--;
		z|=dfs2(s);
		a[s]++;
		a[s+1]++;
		a[s+2]++;
	}
	if(a[s]>0&&a[s+1]>0&&a[s+2]>0&&a[s+3]>0){
		a[s]--;
		a[s+1]--;
		a[s+2]--;
		a[s+3]--;
		z|=dfs2(s);
		a[s]++;
		a[s+1]++;
		a[s+2]++;
		a[s+3]++;
	}
	if(a[s]>0&&a[s+1]>0&&a[s+2]>0&&a[s+3]>0&&a[s+4]>0){
		a[s]--;
		a[s+1]--;
		a[s+2]--;
		a[s+3]--;
		a[s+4]--;
		z|=dfs2(s);
		a[s]++;
		a[s+1]++;
		a[s+2]++;
		a[s+3]++;
		a[s+4]++;
	}
	return z;
}
void dfs(int s){
	if(s==n+1){
		int cnt=0;
		if(k==0)cnt|=dfs2(1);
		if(k==1){
			for(int i=1;i<=n;i++){
				if(cnt)break;
				a[i]++;
				cnt|=dfs2(1);
				a[i]--;
			}
		}
		if(k==2){
			for(int i=1;i<=n;i++){
				a[i]++;
				if(cnt)break;
				for(int j=i;j<=n;j++){
					a[j]++;
					cnt|=dfs2(1);
					if(cnt)break;
					a[j]--;
				}
				a[i]--;
			}
		}
		ans+=cnt;
		return;
	}
	for(int i=l[s];i<=r[s];i++){
		a[s]=i;
		dfs(s+1);
	}
	return;
}
int main(){
	cin>>t;
	while(t--){
		ans=0;
		cin>>n>>k;
		for(int i=1;i<=n;i++){
			scanf("%d%d",&l[i],&r[i]);
		}
		dfs(1);
		printf("%d\n",ans);
	}
	return 0;
}