#21,23,24,29,32,33,44,45,46,47,48WA掉了

#include<bits/stdc++.h>
using namespace std;
int t,n,pai[20],ans=0x3f3f3f3f;
void dfs(int diu){
    if(diu>=ans) return;
    for(int i=3;i<=10;i++){
	  	if(!pai[i]) continue;
		int paishu=1;
		for(int j=i+1;j<=15;j++){
			if(paishu>4){
				for(int k=i;k<j;k++) pai[k]--;
				dfs(diu+1);
				for(int k=i;k<j;k++) pai[k]++;
			}
			if(!pai[j]) break;
			paishu++;
		}
	}
	for(int i=3;i<=12;i++){
		if(pai[i]<2) continue;
		int paishu=1;
		for(int j=i+1;j<=15;j++){
			if(paishu>2){
				for(int k=i;k<j;k++) pai[k]-=2;
				dfs(diu+1);
				for(int k=i;k<j;k++) pai[k]+=2;
			}
			if(pai[j]<2) break;
			paishu++;
		}
	}
	for(int i=3;i<=13;i++){
		if(pai[i]<3) continue;
		int paishu=1;
		for(int j=i+1;j<=15;j++){
			if(paishu>1){
				for(int k=i;k<j;k++) pai[k]-=3;
				dfs(diu+1);
				for(int k=i;k<j;k++) pai[k]+=3;
			}
			if(pai[j]<3) break;
			paishu++;
		}
	}
	int t[5]={0};
	for(int i=2;i<=15;i++){
		if(pai[i]<5) t[pai[i]]++;
		else{
			t[0]=pai[i];
			while(t[0]>4) t[4]++,t[0]-=4;
			t[t[0]]++;
		}
	}
	t[0]=t[1]+t[2]+t[3]+t[4];
	for(int i=1;i<=t[4];i++){
		if(t[2]>1) t[2]-=2,t[0]-=2;
		else if(t[1]>1) t[1]-=2,t[0]-=2;
		else break;
	}
	for(int i=1;i<=t[3];i++){
		if(t[2]) t[2]--,t[0]--;
		else if(t[1]) t[1]--,t[0]--;
		else break;
	}
	ans=min(ans,t[0]+diu);
	return;
}
int main(){
	cin>>t>>n;
	while(t--){
		for(int i=1;i<=n;i++){
			int x,y;cin>>x>>y;
			if(x==1) pai[14]++;
			else if(!x) pai[15]++;
			else pai[x]++;
		}
		dfs(0);
	   cout<<ans<<"\n";
	   memset(pai,0,sizeof(pai));
		ans=0x3f3f3f3f;
	}
	return 0;
}