#include<bits/stdc++.h>
using namespace std;
const int N = 24;
int T,n,mp[N],ans=1e9,mp2[N];
struct T{
	int num;
	int col;
}a[N];
/*
1 13
8 2
6 3
8 4
12 3
3 2
13 1
10 4
9 2
7 1
2 2
8 3
4 2
5 2
*/
void dfs(int cnt,int y){
	if(cnt>=ans){
		return;
	}
	if(y==0){
		ans=min(ans,cnt);
		return;
	}
	for(int i=1;i<=12;i++){
		int tot=0;
		for(int j=i;j<=12;j++){
			if(mp[j]>=1){
				tot++;
			}
			else break;
		}
		if(tot>=5){
			for(int j=i;j<=i+tot-1;j++){
				mp2[mp[j]]--;
				mp[j]--;
				mp2[mp[j]]++;
				if((j-i+1)>=5){
					dfs(cnt+1,y-(j-i+1));
					for(int k=i;k<=j;k++){
						mp2[mp[k]]--;
						mp[k]++;
						mp2[mp[k]]++;
					}
				}
			}
		}
		tot=0;
		for(int j=i;j<=12;j++){
			if(mp[j]>=2){
				tot++;
			}
			else break;
		}
		if(tot>=3){
			for(int j=i;j<=i+tot-1;j++){
				mp2[mp[j]]--;
				mp[j]-=2;
				mp2[mp[j]]++;
				if((j-i+1)>=3){
					dfs(cnt+1,y-(j-i+1)*2);
					for(int k=i;k<=j;k++){
						mp2[mp[k]]--;
						mp[k]+=2;
						mp2[mp[k]]++;
					}
				}
			}
		}
		tot=0;
		for(int j=i;j<=12;j++){
			if(mp[j]>=3){
				tot++;
			}
			else break;
		}
		if(tot>=3){
			for(int j=i;j<=i+tot-1;j++){
				mp2[mp[j]]--;
				mp[j]-=3;
				mp2[mp[j]]++;
				if((j-i+1)>=3){
					dfs(cnt+1,y-(j-i+1)*3);
					for(int k=i;k<=j;k++){
						mp2[mp[k]]--;
						mp[k]+=3;
						mp2[mp[k]]++;
					}
				}
			}
		}
	}
	bool flag=true;
	int tmp=0;
	for(int i=1;i<=12;i++){
		if(mp[i]>=1){
			tmp++;
			if(tmp>=5){
				flag=false;
				break;
			}	
		}
		else{
			tmp=0;
		}
	}
	tmp=0;
	for(int i=1;i<=12;i++){
		if(mp[i]>=2){
			tmp++;
			if(tmp>=3){
				flag=false;
				break;
			}
		}
		else{
			tmp=0;
		}
	}
	tmp=0;
	for(int i=1;i<=12;i++){
		if(mp[i]>=3){
			tmp++;
			if(tmp>=3){
				flag=false;
				break;
			}
		}
		else{
			tmp=0;
		}
	}
	if(flag){
		if(mp[14]==1&&mp[15]==0){
			mp2[1]++;
		}
		else if(mp[14]==0&&mp[15]==1){
			mp2[1]++;
		}
		else if(mp[14]==1&&mp[15]==1){
			mp2[2]++;
		}
		int tot=0,z=mp2[1]/2;
		if(mp2[4]>=z){
			tot=tot+mp2[4]-z;
			mp2[1]-=z*2;
		}
		else{
			tot=tot+mp2[4];
			mp2[1]-=mp2[4]*2;
			mp2[4]=0;
		}
		if(mp2[4]>=mp2[2]){
			tot=tot+mp2[4];
			mp2[4]=0;
			mp2[2]=0; 
		}
		else{
			tot=tot+mp2[4];
			mp2[2]-=mp2[4];
			mp2[4]=0;
		}
		if(mp2[3]>=mp2[1]){
			tot=tot+mp2[1];
			mp2[3]-=mp2[1];
			mp2[1]=0;
		}
		else{
			tot=tot+mp2[3];
			mp2[1]-=mp2[3];
			mp2[3]=0;
		}
		if(mp2[3]>=mp2[2]){
			tot=tot+mp2[3];
			mp2[3]=0;
			mp2[2]=0;
		}
		else{
			tot=tot+mp2[3];
			mp2[2]-=mp2[3];
			mp2[3]=0;
		}
		tot=tot+mp2[2]+mp2[1];
		mp2[2]=0;
		mp2[1]=0;
		dfs(cnt+tot,0);
	}
}
int main(){
	cin>>T>>n;
	while(T--){
		for(int i=0;i<=17;i++) mp[i]=0;
		for(int i=0;i<=4;i++) mp2[i]=0;
		for(int i=1;i<=n;i++){
			cin>>a[i].num>>a[i].col;
			if(a[i].num==1) a[i].num=14;
			if(a[i].num==2) a[i].num=15;
			if(a[i].num==0&&a[i].col==1) a[i].num=16;
			if(a[i].num==0&&a[i].col==2) a[i].num=17;
			mp[a[i].num]++; 
		}
		for(int i=3;i<=17;i++){
			mp[i-2]=mp[i];
		}
		for(int i=1;i<=13;i++){
			mp2[mp[i]]++;
		}
		ans=1e9;
		dfs(0,n);
		cout<<ans<<endl;
	} 
	return 0;
}