#include<bits/stdc++.h>
using namespace std;
int num[20];
int T,n;
int ans;
void dfs(int cnt,int k)
{
	ans=min(cnt+k,ans);
	if(!k)
	{
		return;
	}
	if(ans<=cnt)return;
	int tot;
	
	tot=0;
	if(k>=9)
	for(int j=3;j<=14;j++)
	{
		
		if(num[j]>=3 && j!=14)
			tot++;
		else
		{
			if(tot>=2)
			{
				for(int l=3;l<=tot;l++)
				{
					for(int p=0;p<l;p++)
						num[j-p]-=3;
					for(int t=j;t>=j-tot+l;t--)
					{
						num[t]+=3;
						num[t-l]-=3;
						dfs(cnt+1,k-l*3);
					}
					for(int p=0;p<l;p++)
						num[j-tot+p]+=3;
				}
			}
			if(tot>=1 && j==14 && num[1]>=3)
			{
				num[1]-=3;
				num[13]-=3;
				for(int l=2;l<=tot;l++)
				{
					num[j-l]-=3;
					dfs(cnt+1,k-(l+1)*3);
				}
				for(int p=1;p<=tot;p++)
					num[j-p]+=3;
				num[1]+=3;
			}
			tot=0;
		}
	}
	tot=0;
	if(k>=6)
	for(int j=3;j<=14;j++)
	{
		if(num[j]>=2 && j!=14)tot++;
		else
		{
			if(tot>=3)
			{
				for(int l=3;l<=tot;l++)
				{
					for(int p=0;p<l;p++)
						num[j-p]-=2;
					for(int t=j;t>=j-tot+l;t--)
					{
						num[t]+=2;
						num[t-l]-=2;
						dfs(cnt+1,k-l*2);
					}
					for(int p=0;p<l;p++)
						num[j-tot+p]+=2;
				}
			}
			if(tot>=2 && j==14 && num[1]>=2)
			{
				num[1]-=2;
				num[j-1]-=2;
				for(int l=2;l<=tot;l++)
				{
					num[j-l]-=2;
					dfs(cnt+1,k-(l+1)*2);
				}
				for(int p=1;p<=tot;p++)
					num[j-p]+=2;
				num[1]+=2;
			}
			tot=0;
		}
	}
	tot=0;
	if(k>=5)
	for(int j=3;j<=14;j++)
	{
		if(num[j] && j!=14)tot++;
		else
		{
			if(tot>=5)
			{
				for(int l=5;l<=tot;l++)
				{
					for(int p=0;p<l;p++)
						num[j-p]--;
					for(int t=j;t>=j-tot+l;t--)
					{
						num[t]++;
						num[t-l]--;
						dfs(cnt+1,k-l);
					}
					for(int p=0;p<l;p++)
						num[j-tot+p]++;
				}
			}
			if(tot>=4 && j==14 && num[1])
			{
				num[1]=0;
				for(int p=1;p<=3;p++)
					num[j-p]--;
				for(int l=4;l<=tot;l++)
				{
					num[j-l]--;
					dfs(cnt+1,k-l-1);
				}
				for(int p=1;p<=tot;p++)
					num[j-p]++;
				num[1]++;
			}
			tot=0;
		}
	}
	if(k>=2)
	for(int j=1;j<=13;j++)
	{
		if(num[j]>=2)
		{
			num[j]-=2;
			dfs(cnt+1,k-2);
			num[j]+=2;
		}
	}
	if(num[14] && num[15])
	{
		num[14]=0;
		num[15]=0;
		dfs(cnt+1,k-2);
		num[14]=1;
		num[15]=1;
	}
	if(k>=4)
	for(int j=1;j<=13;j++)
	{
		if(num[j]==4)
		{
			num[j]-=4;
			dfs(cnt+1,k-4);
			num[j]+=4;
		}
	}
	if(k>=3)
	for(int j=1;j<=13;j++)
	{
		if(num[j]>=3)
		{
			num[j]-=3;
			dfs(cnt+1,k-3);
			num[j]+=3;
		}
	}
//			cout<<i;
	if(k>=5){
		for(int j=1;j<=13;j++)
		{
			if(num[j]>=3)
			{
				for(int l=1;l<=13;l++)
				{
					if(l==j)continue;
					if(num[l]>=2)
					{
						num[l]-=2;num[j]-=3;
						dfs(cnt+1,k-5);
						num[l]+=2;num[j]+=3;
					}
				}
			}
		}
	}
	if(k>=4)
	for(int j=1;j<=13;j++)
	{
		if(num[j]>=3)
		{
			num[j]-=3;
			for(int l=1;l<=15;l++)
			{
				if(l==j)continue;
				if(num[l])
				{
					num[l]--;
					dfs(cnt+1,k-4);
					num[l]++;
				}
			}
			num[j]+=3;
		}
	}
//			cout<<i;
	if(k>=8){
		for(int j=1;j<=13;j++)
		{
			if(num[j]==4)
			{
				num[j]-=4;
				for(int l=1;l<=13;l++)
				{
					if(l==j)continue;
					if(num[l]>=2)
					{
						num[l]-=2;
						for(int p=1;p<=13;p++)
						{
							if(p==j)continue;
							if(num[p]>=2)
							{
								num[p]-=2;
								dfs(cnt+1,k-8);
								num[p]+=2;
							}
						}
						num[l]+=2;
					}
				}
				num[j]+=4;
			}
		}
	}
	if(k>=6)
	for(int j=1;j<=13;j++)
	{
		if(num[j]==4)
		{
			num[j]=0;
			for(int l=1;l<=15;l++)
			{
				if(l==j)continue;
				if(num[l])
				{
					num[l]--;
					for(int p=1;p<=15;p++)
					{
						if(p==l)continue;
						if(num[p])
						{
							num[p]--;
							dfs(cnt+1,k-6);
							num[p]++;
						}
					}
					num[l]++;
				}
			}
			num[j]+=4;
		}
	}
//			cout<<i;
}

int main()
{
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	cin>>T;
	cin>>n;
	while(T--)
	{
		ans=n;
		memset(num,0,sizeof num);
		for(int i=1;i<=n;i++)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			if(x!=0)
			num[x]++;
			else
			{
				if(y==1)num[14]++;
				else num[15]++;
			}
		}
		dfs(0,n);
		cout<<ans<<endl;
	}
}