#include <bits/stdc++.h>
using namespace std;
int pk[17];
int t,n;
int ans;
void dfs(int u)
{
    if(u>=ans) return;
    int k=0;
    for(int i=3;i<=14;i++)
    {
        if(pk[i]==0) k=0;
        else
        {
            k++;
            if(k>=5)
            {
                for(int st=i-k+1;st<=i-5+1;st++)
				{
                	for(int j=st+5-1;j<=i;j++)
					{
						for(int l=i-k+1;l<=j;l++) pk[l]-=1;
                		dfs(u+1);
                		for(int l=i-k+1;l<=j;l++) pk[l]+=1;
					}
				} 
            }
        }
    }
    k=0;
    for(int i=3;i<=14;i++)
    {
        if(pk[i]<2) k=0;
        else
        {
            k++;
            if(k>=3)
            {
                for(int st=i-k+1;st<=i-3+1;st++)
				{
                	for(int j=st+3-1;j<=i;j++)
					{
						for(int l=i-k+1;l<=j;l++) pk[l]-=2;
                		dfs(u+1);
                		for(int l=i-k+1;l<=j;l++) pk[l]+=2;
					}
				} 
            }
        }
    }
    k=0;
    for(int i=3;i<=14;i++)
    {
        if(pk[i]<3) k=0;
        else
        {
            k++;
            if(k>=2)
            {
                for(int st=i-k+1;st<=i-2+1;st++)
				{
                	for(int j=st+2-1;j<=i;j++)
					{
						for(int l=i-k+1;l<=j;l++) pk[l]-=3;
                		dfs(u+1);
                		for(int l=i-k+1;l<=j;l++) pk[l]+=3;
					}
				} 
            }
        }
    }
    for(int i=1;i<=14;i++)
    {
        if(pk[i]>=4)
        {pk[i]-=4;
            for(int j=2;j<=14;j++)
            {
                for(int l=2;l<=14;l++)
                {
                	if(!pk[j] || !pk[l]) continue;
                	if(j==l && pk[k]<2) continue;
                	pk[j]--;pk[l]--;
                	dfs(u+1);
                	pk[j]++;pk[l]++;
				}
            }
            for(int j=1;j<=14;j++)
            {
            	for(int l=j+1;l<=14;l++)
            	{
            		if(pk[j]<2 || pk[l]<2 || j==i || l==i) continue;
            		pk[j]-=2;pk[l]-=2;
            		dfs(u+1);
            		pk[j]+=2;pk[l]+=2;
				}
			}pk[i]+=4;
        }
        if(pk[i]>=3)
        {
            for(int j=2;j<=15;j++)
            {
                if(i==j || pk[j]==0) continue;
                if(pk[j]>=1) pk[i]-=3,pk[j]--,dfs(u+1),pk[i]+=3,pk[j]++;
                if(pk[j]>=2) pk[i]-=3,pk[j]-=2,dfs(u+1),pk[i]+=3,pk[j]+=2;
            }
        }
    }
    for(int i=1;i<=15;i++) if(pk[i]) u++;
    ans=min(ans,u);
}
int main()
{
    scanf("%d%d",&t,&n);
    while(t--)
    {
        ans=114501419;
        for(int i=1;i<=n;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            if(a==0) pk[15]++;
            else pk[a]++;
        }
        dfs(0);
        printf("%d\n",ans);
        memset(pk,0,sizeof pk);
    }
}