#include <bits/stdc++.h>
using namespace std;
int n,t,a,b,f[20],ans;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
void dfs(int x){
	if(ans<=x)return;
	int k=0;
	for(int i=3;i<=14;i++)
		if(!f[i])
			k=0;
		else{
			k++;
			if(k>=5){
				for(int j=i;j>=i-k+1;j--)
					f[j]--;
				dfs(x+1);
				for(int j=i;j>=i-k+1;j--)
					f[j]++;	
			}
		}
	k=0;
	for(int i=3;i<=14;i++)
		if(f[i]<2)
			k=0;
		else{
			k++;
			if(k>=3){
				for(int j=i;j>=i-k+1;j--)
					f[j]-=2;
				dfs(x+1);
				for(int j=i;j>=i-k+1;j--)
					f[j]+=2;
			}
		}
	k=0;
	for(int i=3;i<=14;i++)
		if(f[i]<3)
			k=0;
		else{
			k++;
			if(k>=2){
				for(int j=i;j>=i-k+1;j--)
					f[j]-=3;
				dfs(x+1);
				for(int j=i;j>=i-k+1;j--)
					f[j]+=3;
			}
		}
	for(int i=2;i<=14;i++)
		if(f[i]>2&&f[i]<4){
			f[i]-=3;
			for(int j=2;j<=15;j++){
				if(f[j]<1||j==i)
					continue;
				f[j]--;
				dfs(x+1);
				f[j]++;
			}
			for(int j=2;j<=14;j++){
				if(f[j]<2||j==i)
					continue;
				f[j]-=2;
				dfs(x+1);
				f[j]+=2;
			}
			f[i]+=3;	
		}
		else if(f[i]>3){
			f[i]-=3;
			for(int j=2;j<=15;j++){
				if(f[j]<1||j==i)
					continue;
				f[j]--;
				dfs(x+1);
				f[j]++;
			}
			for(int j=2;j<=14;j++){
				if(f[j]<2||j==i)
					continue;
				f[j]-=2;
				dfs(x+1);
				f[j]+=2;
			}
			f[i]+=3;
			f[i]-=4;
			for(int j=2;j<=15;j++){
				if(f[j]<1||j==i)
					continue;
				f[j]--;
				for(int k=2;k<=15;k++){
					if(f[k]<1)
						continue;
					f[k]--;
					dfs(x+1);
					f[k]++;	
				}
				f[j]++;
			}
			for(int j=2;j<=14;j++){
				if(f[j]<2||j==i)
					continue;
				f[j]-=2;
				for(int k=2;k<=14;k++){
					if(f[k]<2)
						continue;
					f[k]-=2;
					dfs(x+1);
					f[k]+=2;
				}
				f[j]+=2;
			}
			f[i]+=4;
		}
	for(int i=2;i<=15;i++)if(f[i])x++;
	ans=min(ans,x);
}
int main(){
	t=read();
	n=read();
	while(t--){
		ans=0x3f;
		memset(f,0,sizeof(f));
		for(int i=1;i<=n;i++){
			a=read();
			b=read();
			if(a==0)
				f[15]++;
			else if(a==1)
				f[14]++;
			else 
				f[a]++;
		}
		dfs(0);
		printf("%d\n",ans);
	}
}