#include<cstdio>
#include<queue>
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
int T,n;
int sum[15];
int ans=2147483647;
void dfs(int cnt){
    if(cnt>=ans)return;
    bool flag=false;
    int k1=0,k2=0,k3=0;
    for(int i=0;i<=11;i++){
        if(sum[i]<1)k1=0;
        else{
            k1++;
            if(k1>=5){
				for(int j=i;j>=i-k1+1;j--)--sum[j];
				dfs(cnt+1);flag=true;
				for(int j=i;j>=i-k1+1;j--)++sum[j];
			}
        }
        if(sum[i]<2)k2=0;
        else{
            k2++;
            if(k2>=3){
                for(int j=i;j>=i-k2+1;j--)sum[j]-=2;
                dfs(cnt+1);flag=true;
                for(int j=1;j>=i-k2+1;j--)sum[j]+=2;
            }
        }
        if(sum[i]<3)k3=0;
        else{
            k3++;
            if(k3>=2){
                for(int j=i;j>=i-k3+1;j--)sum[j]-=3;
                dfs(cnt+1);flag=true;
                for(int j=1;j>=i-k3+1;j--)sum[j]+=3;
            }
        }
    }
    for(int i=0;i<=14;i++){
        if(sum[i]>=3){
            for(int j=0;j<=12;j++){
                if(i==j)continue;
                if(sum[j]>=2){
                    sum[i]-=3;sum[j]-=2;
                    dfs(cnt+1);flag=true;
                    sum[i]+=3;sum[j]+=2;
                }
                if(sum[j]>=1){
                    sum[i]-=3;--sum[j];
                    dfs(cnt+1);flag=true;
                    sum[j]-=3;++sum[j];
                }
            }
        }
        if(sum[i]>=4){
            for(int j=0;j<=12;j++){
                if(i==j)continue;
                for(int k=0;k<=12;k++){
                    if(j==k||k==i)continue;
                    if(sum[j]>=2&&sum[k]>=2){
                        sum[i]-=4;sum[j]-=2;sum[k]-=2;
                        dfs(cnt+1);flag=true;
                        sum[i]+=4;sum[j]+=2;sum[k]+=2;
                    }
                    if(sum[j]&&sum[k]){
                        sum[i]-=4;--sum[j];--sum[k]-=1;
                        dfs(cnt+1);flag=true;
                        sum[i]+=4;++sum[j];++sum[k];
                    }
                }
            }
        }
    }
    if(sum[13]&&sum[14]){
        --sum[13];--sum[14];
        dfs(cnt+1);flag=true;
        ++sum[13];++sum[14];
    }
    for(int i=0;i<=14;i++)if(sum[i])cnt++;
    ans=min(ans,cnt);
}
int main(){
    scanf("%d%d",&T,&n);
    while(T--){
        ans=2147483647;
        for(int i=0;i<=14;i++)sum[i]=0;
        for(int i=1;i<=n;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            if(a>=3)sum[a-3]++;
            else{
                if(a==0)sum[12+b]++;
                else if(a==1)sum[11]++;
                else if(a==2)sum[12]++;
            }
        }
        dfs(0);
        printf("%d\n",ans);
    }
}