#include<bits/stdc++.h>
using namespace std;
int T,n,minn=0x3f3f3f3f;
int a[20];
void dfs(int n,int x){
	if(x>=minn) return ;
	if(n==0){
		minn=min(minn,x);
		return ;
	}
	int maxx=0; 
	for(int i=2;i<=14;i++){
		if(a[i]<3) continue;
		a[i]-=3;
		dfs(n-3,x+1);
		for(int j=2;j<=16;j++){
			if(a[j]<1||i==j) continue;
			a[j]--;
			dfs(n-4,x+1);
			a[j]++;
		}
		for(int j=2;j<=14;j++){
			if(a[j]<2||i==j) continue;
			a[j]-=2;
			dfs(n-5,x+1);
			a[j]+=2;
		}
		a[i]+=3;
	}
	maxx=0; 
	for(int i=3;i<=14;i++){
		if(a[i]<3)
			maxx=0;
		else{
			maxx++;
			if(maxx>=2){
				for(int j=i;j>=i-maxx+1;j--) a[j]-=3;
				dfs(n-maxx*3,x+1);
				for(int j=i;j>=i-maxx+1;j--) a[j]+=3;
			}
		}
	}
	maxx=0;
	for(int i=3;i<=14;i++){
		if(a[i]==0)
			maxx=0;
		else{
			maxx++;
			if(maxx>=5){
				for(int j=i;j>=i-maxx+1;j--) a[j]--;
				dfs(n-maxx,x+1);
				for(int j=i;j>=i-maxx+1;j--) a[j]++;
			}
		}
	}
	maxx=0; 
	for(int i=3;i<=14;i++){
		if(a[i]<2)
			maxx=0;
		else{
			maxx++;
			if(maxx>=3){
				for(int j=i;j>=i-maxx+1;j--) a[j]-=2;
				dfs(n-maxx*2,x+1);
				for(int j=i;j>=i-maxx+1;j--) a[j]+=2;
			}
		}
	}
	for(int i=2;i<=14;i++){
		if(a[i]<4) continue;
		a[i]-=4;
		for(int j=2;j<=16;j++){
			if(a[j]==0) continue;
			a[j]--;
			for(int k=2;k<=16;k++){
				if(a[k]==0) continue;
				a[k]--;
				dfs(n-6,x+1);
				a[k]++;
			}
			a[j]++;
		}
		for(int j=2;j<=14;j++){
			if(a[j]<2) continue;
			a[j]-=2;
			for(int k=2;k<=14;k++){
				if(a[k]<2) continue;
				a[k]-=2;
				dfs(n-6,x+1);
				a[k]+=2;
			}
			a[j]+=2;
		}
		a[i]+=4;
	}
	for(int i=2;i<=14;i++){
		if(a[i]>=2){
			a[i]-=2;
			dfs(n-2,x+1);
			a[i]+=2;
		}
	}
	if(a[15]!=0&&a[16]!=0){
		a[15]--,a[16]--;
		dfs(n-2,x+1);
		a[15]++,a[16]++;
	}
	int y=x;
	for(int i=2;i<=16;i++){
		if(a[i]!=0){
			y++;
		}
	}
	dfs(0,y);
}
int main(){
	cout.tie(0);
	cin>>T>>n;
	while(T--){
		memset(a,0,sizeof(a));
		minn=0x3f3f3f3f;
		for(int i=1,x,y;i<=n;i++){
			cin>>x>>y;
			if(x!=0&&x!=1) a[x]++;
			else if(x==1) a[14]++;
			else a[14+y]++;
		}
		dfs(n,0);
		cout<<minn<<endl;
	}
	return 0;
}

悬关，感谢