#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,n;
int King,king;
int num[20];
int ans;
void init()
{
	for(int i=0;i<20;i++)
		num[i]=0;
	ans=INT_MAX;
	King=king=0;
	return ;
}
bool no()
{
	for(int i=2;i<=14;i++)
		if(num[i]>0)
			return false;
	if(king>0||King>0)
		return false;
	return true;
}
void dfs(int round)
{
	
	int ro=round;
	if(round>ans)
		return;
	if(no())
	{
		ans=min(round,ans);
	}
	if(King==1&&king==1)
	{
		King=0,king=0;
		dfs(round+1);
		King=1,king=1;
	}
	int k=0;
	for(int i=3;i<=14;i++)
	{
		if(num[i]>0)
			k++;
		else
			k=0;
		if(k>=5)
		{
			int begin=i-k+1;
			int begie=i-5+1;
			for(int be=begin;be<=begie;be++)
			{
				for(int j=be;j<=i;j++)
					num[j]--;
				dfs(round+1);
				for(int j=be;j<=i;j++)
					num[j]++;			
			}
		}
	}
	k=0;
	for(int i=3;i<=14;i++)
	{
		if(num[i]>1)
			k++;
		else
			k=0;
		if(k>=3)
		{
			int begin=i-k+1;
			int begie=i-3+1;
			for(int be=begin;be<=begie;be++)
			{
				for(int j=be;j<=i;j++)
					num[j]-=2;
				dfs(round+1);
				for(int j=be;j<=i;j++)
					num[j]+=2;			
			}
		}
	}
	k=0;
	for(int i=3;i<=14;i++)
	{
		if(num[i]>2)
			k++;
		else
			k=0;
		if(k>=2)
		{
			int begin=i-k+1;
			int begie=i-2+1;
			for(int be=begin;be<=begie;be++)
			{
				for(int j=be;j<=i;j++)
					num[j]-=3;
				dfs(round+1);
				for(int j=be;j<=i;j++)
					num[j]+=3;			
			}
		}
	}
	for(int i=2;i<=14;i++)
	{
		if(num[i]>=3)
		{
			num[i]-=3;
			dfs(round+1);
			num[i]+=3;
			for(int j=2;j<=14;j++)
			{
				if(num[j]>=1&&i!=j)
				{
					num[j]-=1;num[i]-=3;
					dfs(round+1);
					num[j]+=1;num[i]+=3;
				}
				if(num[j]>=2&&i!=j)
				{
					num[j]-=2;num[i]-=3;
					dfs(round+1);
					num[j]+=2;num[i]+=3;
				}
			}
			if(King==1)
			{
				num[i]-=3;
				King--;
				dfs(round+1);
				King++;
				num[i]+=3;
			}
			if(king==1)
			{
				num[i]-=3;
				king--;
				dfs(round+1);
				king++;
				num[i]+=3;
			}
		}
		if(num[i]==4)
		{
			num[i]=0;
			dfs(round+1);
			num[i]=4;
			for(int j=2;j<=14;j++)
			{
				for(k=2;k<=14;k++)
				{
					if(num[j]>=1&&num[k]>=1&&i!=j&&j!=k&&i!=k)
					{
						num[i]-=4;num[j]-=1;num[k]-=1;
						dfs(round+1);
						num[i]+=4;num[j]+=1;num[k]+=1;
					}
					if(num[j]>=2&&num[k]>=2&&i!=j&&j!=k&&i!=k)
					{
						num[i]-=4;num[j]-=2;num[k]-=2;
						dfs(round+1);
						num[i]+=4;num[j]+=2;num[k]+=2;
					}
				}
			}
			if(King==1)
			{
				for(int j=2;j<=14;j++)
				{
					if(num[j]>0&&i!=j)
					{
						num[i]-=4;
						num[j]-=1;
						King-=1;
						dfs(round+1);
						num[i]+=4;
						num[j]+=1;
						King+=1;
					}
				}
			}
			if(king==1)
			{
				for(int j=2;j<=14;j++)
				{
					if(num[j]>0&&i!=j)
					{
						num[i]-=4;
						num[j]-=1;
						king-=1;
						dfs(round+1);
						num[j]-=4;
						num[j]+=1;
						king+=1;
					}
				}
			}
		}
	}
	if(King==1||king==1)
		ro++;
	for(int i=2;i<=14;i++)
	{
		if(num[i]!=0)
			ro++;
	}
	ans=min(ro,ans);
	return ;
}
int solve()
{
	init();
	for(int i=1;i<=n;i++)
	{
		int a,b;
		cin>>a>>b;
		if(a==0)
			if(b==1)
				King=1;
			else
				king=1;
		else if(a==1)
			num[14]++;
		else
			num[a]++;
	}
	dfs(0);
	return ans;
}
signed main()
{
	cin>>T>>n;
	while(T--)
		cout<<solve()<<endl;
	return 0;
}