#include<bits/stdc++.h>
using namespace std;
#define int register int
#define ll long long

inline signed read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}

ll pai[20];
ll ans=1e9;

void dfs(ll sum)
{
	if(sum>=ans) return;
	int k=0;
	for(int i=3;i<=14;++i)//3s
	{
		if(pai[i]>=3) 
		{
			++k;
			if(k>=2)
			{
				for(int j=i;j>=i-k+1;--j) pai[j]-=3;
				dfs(sum+1);
				for(int j=i;j>=i-k+1;--j) pai[j]+=3;
			}
		}
		else k=0;
	}
	k=0;
	for(int i=3;i<=14;++i)//2s
	{
		if(pai[i]>=2) 
		{
			++k;
			if(k>=3)
			{
				for(int j=i;j>=i-k+1;--j) pai[j]-=2;
				dfs(sum+1);
				for(int j=i;j>=i-k+1;--j) pai[j]+=2;
			}
		}
		else k=0;
	}
	k=0;
	for(int i=3;i<=14;++i)//1s
	{
		if(pai[i]>=1) 
		{
			++k;
			if(k>=5)
			{
				for(int j=i;j>=i-k+1;--j) --pai[j];
				dfs(sum+1);
				for(int j=i;j>=i-k+1;--j) ++pai[j];
			}
		}
		else k=0;
	}
	
	for(int i=2;i<=14;++i)//4
	{
		if(pai[i]>=4)
		{
			pai[i]-=4;//4+2
			for(int j=2;j<=14;++j)//4+2+2
			{
//				if(i==j) continue;
				if(pai[j]>=2)
				{
					pai[j]-=2;
					for(int k=2;k<=14;++k)
					{
						if(pai[k]>=2)
						{
							pai[k]-=2;
							dfs(sum+1);
							pai[k]+=2;
						}
					}
					pai[j]+=2;
				}
			}
			for(int j=2;j<=16;++j)//4+1+1
			{
//				if(i==j) continue;
				if(pai[j]>=1)
				{
					pai[j]--;
					for(int k=2;k<=16;++k)
					{
						if(pai[k])
						{
							pai[k]--;
							dfs(sum+1);
							pai[k]++;
						}
					}
					pai[j]++;
				}
			}
			pai[i]+=4;
		}
	}
	
	for(int i=2;i<=14;++i)//3+2
	{
		if(pai[i]==3)
		{
			pai[i]-=3;
			for(int j=2;j<=14;++j)
			{
//				if(j==i) continue;
				if(pai[j]>=2)
				{
					pai[j]-=2;
					dfs(sum+1);
					pai[j]+=2;
				}
			}
			pai[i]+=3;
		}
	}
	for(int i=2;i<=14;++i)//3+1
	{
		if(pai[i]==3)
		{
			pai[i]-=3;
			for(int j=2;j<=16;++j)
			{
//				if(j==i) continue;
				if(pai[j]>=1)
				{
					pai[j]-=1;
					dfs(sum+1);
					pai[j]+=1;
				}
			}
			pai[i]+=3;
		}
	}
	
	for(int i=2;i<=16;++i) if(pai[i]) ++sum;
	if(pai[15]&&pai[16]) --sum;
	ans=min(ans,sum);
}

signed main()
{
	int T=read(),n=read();
	while(T--)
	{
		for(int i=0;i<=19;++i) pai[i]=0;
		for(int i=1;i<=n;++i)
		{
			int temp=read(),c=read();
			if(temp==1) temp=14;
			if(!temp) temp=14+c;
			++pai[temp];
		}
		ans=0xfffffff;
		dfs(0);
		cout<<ans<<endl;
	}
	return 0;
}