#include<bits/stdc++.h>
using namespace std;
int t,n,ans,x,y,a[17];
int check(){
	int s=0;
	for(int i=2;i<=16;i++) if(a[i]) s++;
	return s;
}
void dfs(int num,int depth){
	if(num==0){
		ans=min(ans,depth);
		return;
	}
	if(depth>=ans) return;
	ans=min(ans,depth+check());
	for(int i=2;i<=14;i++){
		if(a[i]==4){
			for(int j=2;j<=14;j++){
				if(i==j||a[j]<2) continue;
				for(int k=2;k<=14;k++){
					if(i==k||j==k||a[k]<2) continue;
					a[i]-=4;
					a[j]-=2;
					a[k]-=2;
					dfs(num-8,depth+1);
					a[i]+=4;
					a[j]+=2;
					a[k]+=2;
				}
			}//四带两对 
			for(int j=2;j<=16;j++){
				if(i==j||!a[j]) continue;
				for(int k=2;k<=14;k++){
					if(i==k||j==k||!a[k]) continue;
					a[i]-=4;
					a[j]--;
					a[k]--;
					dfs(num-6,depth+1);
					a[i]+=4;
					a[j]++;
					a[k]++;
				}
			}//四带两个 
			a[i]-=4;
			dfs(num-4,depth+1);
			a[i]+=4;//炸 
		}
		if(a[i]>=3){
			if(i!=2){
				int cnt=1;
				for(int j=i+1;j<=14;j++){
					if(a[j]>=3) cnt++;
					else break;
				}
				if(cnt>=2){
					for(int j=i;j<=i+cnt-1;j++) a[j]-=3;
					dfs(num-3*cnt,depth+1);
					for(int j=i;j<=i+cnt-1;j++) a[j]+=3;	
				}
			}//三顺子 
			for(int j=2;j<=14;j++){
				if(i==j||a[j]<2) continue;
				a[i]-=3;
				a[j]-=2;
				dfs(num-5,depth+1);
				a[i]+=3;
				a[j]+=2;
			}//三带二 
			for(int j=2;j<=16;j++){
				if(i==j||!a[j]) continue;
				a[i]-=3;
				a[j]--;
				dfs(num-4,depth+1);
				a[i]+=3;
				a[j]++;
			}//三带一 
			a[i]-=3;
			dfs(num-3,depth+1);
			a[i]+=3;//三张牌 
		}
		if(a[i]>=2){
			if(i!=2){
				int cnt=1;
				for(int j=i+1;j<=14;j++){
					if(a[j]>=2) cnt++;
					else break;
				}
				if(cnt>=3){
					for(int j=i;j<=i+cnt-1;j++) a[j]-=2;
					dfs(num-2*cnt,depth+1);
					for(int j=i;j<=i+cnt-1;j++) a[j]+=2;
				}
			}//双顺子 
			a[i]-=2;
			dfs(num-2,depth+1);
			a[i]+=2;//一对 
		}
		if(a[i]){
			if(i!=2){
				int cnt=1;
				for(int j=i+1;j<=14;j++){
					if(a[j]) cnt++;
					else break;
				}
				if(cnt>=5){
					for(int j=i;j<=i+cnt-1;j++) a[j]--;
					dfs(num-cnt,depth+1);
					for(int j=i;j<=i+cnt-1;j++) a[j]++;
				}
			}//顺子 
			a[i]--;
			dfs(num-1,depth+1);
			a[i]++;//单张牌 
		}
	}
	if(a[15]&&a[16]){
		a[15]--;
		a[16]--;
		dfs(num-2,depth+1);
		a[15]++;
		a[16]++;
	}//火箭 
	if(a[15]){
		a[15]--;
		dfs(num-1,depth+1);
		a[15]++;
	}//单张小王
	if(a[16]){
		a[16]--;
		dfs(num-1,depth+1);
		a[16]++;
	}//单张大王
}
int main(){
	scanf("%d%d",&t,&n);
	while(t--){
		memset(a,0,sizeof(a));
		ans=1e9;
		for(int i=1;i<=n;i++){
			scanf("%d%d",&x,&y);
			if(x==1) a[14]++;//A用14表示 
			else if(x==0&&y==1) a[15]++;
			else if(x==0&&y==2) a[16]++;
			else a[x]++;
		}
		dfs(n,0);
		printf("%d\n",ans);
	}
	return 0;
}