Code:

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