#include<bits/stdc++.h>
using namespace std;
int pai[20];
int ans=999999999;

void chupai(int n){
	//3 l
	int s3=0;
	for(int i=3;i<=14;i++){
		if(pai[i]>=3)s3++;
		else s3=0;
		if(s3>=2){
			for(int j=i;j>=i-s3+1;j--)pai[j]-=3;
			chupai(n+1);
			for(int j=i;j>=i-s3+1;j--)pai[j]+=3;
		}
	}
	//2 l
	int s2=0;
	for(int i=3;i<=14;i++){
		if(pai[i]>=2)s2++;
		else s2=0;
		if(s2>=3){
			for(int j=i;j>=i-s2+1;j--)pai[j]-=2;
			chupai(n+1);
			for(int j=i;j>=i-s2+1;j--)pai[j]+=2;
		}
	}
	//1 l
	int s=0;
	for(int i=3;i<=14;i++){
		if(pai[i])s++;
		else s=0;
		if(s>=5){
			for(int j=i;j>=i-s+1;j--)pai[j]--;
			chupai(n+1);
			for(int j=i;j>=i-s+1;j--)pai[j]++;
		}
	}
	
	//4+2
	for(int m=2;m<=14;m++){
		if(pai[m]==4){
			pai[m]=0;
			for(int i=2;i<=14;i++){
				for(int j=2;j<=14;j++){
					if(pai[i]>=1&&pai[j]>=1&&i!=j){
						pai[i]--;pai[j]--;
						chupai(n+1);
						pai[i]++;pai[j]++;
					}
					if(pai[i]>=2&&pai[j]>=2&&i!=j){
						pai[i]-=2;pai[j]-=2;
						chupai(n+1);
						pai[i]+=2;pai[j]+=2;
					}
					
				}
			}
			for(int i=2;i<=14;i++){
				if(pai[i]>=2){
					pai[i]-=2;
					chupai(n+1);
					pai[i]+=2;
				}
				if(pai[i]==4){
					pai[i]=0;
					chupai(n+1);
					pai[i]=4;
				}
			}
			pai[m]=4;
		}
	}
	//3+2
	for(int m=2;m<=14;m++){
		if(pai[m]>=3){
			pai[m]-=3;
			for(int i=2;i<=14;i++){
				if(i!=m&&pai[i]>1){
					pai[i]-=2;
					chupai(n+1);
					pai[i]+=2;
				}
			}
			pai[m]+=3;
		}
	}
	//3+1
	for(int m=2;m<=14;m++){
		if(pai[m]>=3){
			pai[m]-=3;
			for(int i=2;i<=14;i++){
				if(i!=m&&pai[i]){
					pai[i]--;
					chupai(n+1);
					pai[i]++;
				}
			}
			pai[m]+=3;
		}
	}
	
	//4
	for(int i=2;i<=14;i++){
		if(pai[i]==4){
			pai[i]=0;
			chupai(n+1);
			pai[i]=4;
		}
	}
	//3
	for(int i=2;i<=14;i++){
		if(pai[i]>=3){
			pai[i]-=3;
			chupai(n+1);
			pai[i]+=3;
		}
	}
	//2
	for(int i=2;i<=14;i++){
		if(pai[i]>=2){
			pai[i]-=2;
			chupai(n+1);
			pai[i]+=2;
		}
	}
	//1 jieshu
	int sum=0;
	for(int i=2;i<=14;i++){
		sum+=pai[i];
	}
	/*for(int i=2;i<=14;i++){
		cout<<pai[i]<<' ';
	}
	cout<<endl;*/
	ans=min(ans,sum+n);
	return ;
	
}
int main(){
	//freopen("1.in","r",stdin);
	//freopen("1.out","w",stdout);
	int t,n;
	scanf("%d%d",&t,&n);
	int a,b;
	for(int i=1;i<=t;i++){
		memset(pai,0,sizeof(pai));
		ans=999999999;
		for(int j=1;j<=n;j++){
			scanf("%d%d",&a,&b);
			if(a==1)a=14;
			pai[a]++;
		}
		chupai(0);
		if(pai[0])ans++;
	    cout<<ans<<endl;
	}
	
	return 0;
}