代码如下：

#include<bits/stdc++.h>
using namespace std;
int t,n,a,b,num[20],ans;
bool flag;
void dfs(int deep){
	if(deep>=ans) return;
	bool q=1;
	for(int i=0;i<=12;i++){
		if(num[i]){
			q=0;
			break;
		}
	}
	if(q){
		ans=deep;
		return;
	}
	for(int i=0;i<=12;i++){
		if(num[i]>=4){
			num[i]-=4;
			dfs(deep+1);
			num[i]+=4;
		}
	}
	for(int i=0;i<=12;i++){
		if(num[i]){
			num[i]--;
			dfs(deep+1);
			num[i]++;
		}
	}
	for(int i=0;i<=12;i++){
		if(num[i]>=2){
			num[i]-=2;
			dfs(deep+1);
			num[i]+=2;
		}
	}
	for(int i=0;i<=12;i++){
		if(num[i]>=3){
			num[i]-=3;
			dfs(deep+1);
			num[i]+=3;
		}
	}
	for(int i=0;i<=12;i++){
		if(num[i]>=3){
			num[i]-=3;
			for(int j=0;j<=12;j++){
				if(i!=j&&num[j]){
					num[j]--;
					dfs(deep+1);
					num[j]++;
				}
			}
			num[i]+=3;
		}
	}
	for(int i=0;i<=12;i++){
		if(num[i]>=3){
			num[i]-=3;
			for(int j=0;j<=12;j++){
				if(i!=j&&num[j]>=2){
					num[j]-=2;
					dfs(deep+1);
					num[j]+=2;
				}
			}
			num[i]+=3;
		}
	}
	int s=0;
	for(int i=0;i<=11;i++){
		if(num[i]){
			s++;
			if(s>=5){
				int k=i;
				while(k>=0&&num[k]){
					num[k]--;
					k--;
				}
				dfs(deep+1);
				for(int j=k+1;j<=i;j++) num[j]++;
			}
		}else s=0;
	}
	s=0;
	for(int i=0;i<=11;i++){
		if(num[i]>=2){
			s++;
			if(s>=3){
				int k=i;
				while(k>=0&&num[k]>=2){
					num[k]-=2;
					k--;
				}
				dfs(deep+1);
				for(int j=k+1;j<=i;j++) num[j]+=2;
			}
		}else s=0;
	}
	s=0;
	for(int i=0;i<=11;i++){
		if(num[i]>=3){
			s++;
			if(s>=2){
				int k=i;
				while(k>=0&&num[k]>=3){
					num[k]-=3;
					k--;
				}
				dfs(deep+1);
				for(int j=k+1;j<=i;j++) num[j]+=3;
			}
		}else s=0;
	}
	for(int i=0;i<=12;i++){
		if(num[i]>=4){
			num[i]-=4;
			for(int j=0;j<=12;j++){
				if(i!=j&&num[j]){
					num[j]--;
					for(int z=0;z<=12;z++){
						if(i!=z&&j!=z&&num[z]){
							num[z]--;
							dfs(deep+1);
							num[z]++;
						}
					}
					num[j]++;
				}
			}
			num[i]+=4;
		}
	}
	for(int i=0;i<=12;i++){
		if(num[i]>=4){
			num[i]-=4;
			for(int j=0;j<=12;j++){
				if(i!=j&&num[j]>=2){
					num[j]-=2;
					for(int z=0;z<=12;z++){
						if(i!=z&&j!=z&&num[z]>=2){
							num[z]-=2;
							dfs(deep+1);
							num[z]+=2;
						}
					}
					num[j]+=2;
				}
			}
			num[i]+=4;
		}
	}
}
int main(){
	scanf("%d%d",&t,&n);
	while(t--){
		flag=0;
		ans=1e9;
		memset(num,0,sizeof(num));
		for(int i=1;i<=n;i++){
			scanf("%d%d",&a,&b);
			if(!a) flag=1;
			else{
				if(a>=3&&a<=13) num[a-3]++;
				else if(a==1) num[11]++;
				else num[12]++;
			}
		}
		dfs(0);
		printf("%d\n",ans);
	}
	return 0;
}