#include<bits/stdc++.h>
using namespace std;

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

int n;
int val[23];
int dp[1<<23];
vector<int> use[10];
vector<int> dat[5];
queue<int> q;

inline void add(int con,int x=0){
    dp[con]=1;
    if(x<=2||x>=5) q.push(con);
    use[x].push_back(con);

    if(x>=1&&x<=4)
    for(int i=0;i<n;i++)
    if(con&(1<<i)){
        dat[x].push_back(val[i]);
        break;
    }
}
inline void shunzi(int id,int len){
    if(use[id].size()<len) return;
    queue<int> q1,q2,q3;
    for(int i=0;i<use[id].size();i++){
        q1.push(dat[id][i]);
        q2.push(use[id][i]);
        q3.push(1);
    }
    while(!q1.empty()){
        int x=q1.front();q1.pop();
        int vx=q2.front();q2.pop();
        int lx=q3.front();q3.pop();
        if(lx>=len) add(vx,id+4);
        for(int i=0;i<use[id].size();i++){
            int y=dat[id][i];
            int z=use[id][i];
            if(y<x+1) continue;
            if(y>x+1) break;
            int vy=vx|z;
            int ly=lx+1;
            q1.push(y);
            q2.push(vy);
            q3.push(ly);
        }        
    }
}
inline void init(){
    memset(dp,0x3f,sizeof(dp));
    memset(val,0,sizeof(val));
    while(q.size()) q.pop();
    for(int i=0;i<=4;i++){
        use[i].clear();
        dat[i].clear();
    }
    for(int i=5;i<=7;i++)
    use[i].clear();
    for(int i=0;i<n;i++){
        val[i]=read();
        int x=read();
        if(val[i]==1) val[i]=14;
        if(val[i]==2) val[i]=1;
    }
    sort(val,val+n);
}
inline void prepare(){
    if(val[0]==0&&val[1]==0) add(3);
    for(int i=0;i<n;i++){
        add((1<<i),1);
        if(i+1<n&&val[i]==val[i+1]){
            if(i+2<n&&val[i]==val[i+2]){
                if(i+3<n&&val[i]==val[i+3]) add((1<<i)|(1<<(i+1))|(1<<(i+2))|(1<<(i+3)),4);
                else add((1<<i)|(1<<(i+1))|(1<<(i+2)),3);
            }
            else if(val[i]>0) add((1<<i)|(1<<(i+1)),2);
        }
    }
    for(int i=0;i<use[3].size();i++){
        int x=use[3][i];
        for(int j=0;j<use[2].size();j++)
        add(x|use[2][j]);

        for(int j=0;j<n;j++)
        if(dat[3][i]!=val[j]) 
        add(x|use[1][j]);
    }
    for(int i=0;i<use[4].size();i++){
        int x=use[4][i];
        for(int j=0;j<use[2].size();j++)
        for(int k=j+1;k<use[2].size();k++)
        add(x|use[2][j]|use[2][k]);

        for(int j=0;j<n;j++)
        if(dat[4][i]!=val[j])
        for(int k=j+1;k<n;k++)
        if(dat[4][i]!=val[k])
        add(x|(1<<j)|(1<<k));
    }

    shunzi(1,5);
    shunzi(2,3);
    shunzi(3,2);
}
inline void solve(){
    int all=(1<<n)-1;
    int range[6]={0,5,6,7,2,1};
    while(!q.empty()){
        int x=q.front();q.pop();
        bool sw=false;
        for(int j=0;j<5;j++){
            int id=range[j];
            bool vis[15];
            memset(vis,0,sizeof(vis));
            for(int i=0;i<use[id].size();i++){
                int y=use[id][i];
                int z=x|y;
                if(x&y) continue;
                if(dp[z]<=dp[x]+1) continue;

                if(z!=all) q.push(z);
                dp[z]=dp[x]+1;
                sw=true;
            }
            if(sw) break;
        }
        if(!sw){
            int add=n;
            for(int i=0;i<n;i++)
            if(x&(1<<i)) add--;
            dp[all]=min(dp[all],dp[x]+add);
        }
    }
    cout<<dp[all]<<endl;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(),cout.tie(0);

    int t=read();
    n=read();
    while(t--){
        init();
        prepare();
        solve();
    }
    return 0;
}