#include <iostream>
#include <cstring>
#define x first 
#define y second
#define ll long long
#define pii pair<ll,ll>
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
using namespace std;
template <typename T>
inline void read(T &f){
	f=1;
	T x=0;
	char ch=gc();
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			f=-1;
		ch=gc();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=gc();
	}
	f*=x;
}
template <typename T>
inline void print(T x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
		print(x/10);
	putchar(x%10+'0');
}
ll T;
ll n;
ll map[25];
ll ans=10000000000;
void srh(ll k){
	if(k>=ans)
		return ;
	ll len=0;
	//shunzi
	//single shunzi
	for(ll i=3;i<=14;i++){
		if(map[i]==0)
			len=0;
		else{
			len++;
			if(len>=5){
				for(ll j=i;j>=i-len+1;j--)
					map[j]--;
				srh(k+1);
				for(ll j=i;j>=i-len+1;j--)
					map[j]++;
			}
		}
	}
	//double shunzi
	len=0;
	for(ll i=3;i<=14;i++){
		if(map[i]<2)
			len=0;
		else{
			len++;
			if(len>=3){
				for(ll j=i;j>=i-len+1;j--)
					map[j]-=2;
				srh(k+1);
				for(ll j=i;j>=i-len+1;j--)
					map[j]+=2;
			}
		}
	}
	//trible shunzi
	len=0;
	for(ll i=3;i<=14;i++){
		if(map[i]<=2)
			len=0;
		else{
			len++;
			if(len>=2){
				for(ll j=i;j>=i-len+1;j--)
					map[j]-=3;
				srh(k+1);
				for(ll j=i;j>=i-len+1;j--)
					map[j]+=3;
			}
		}
	}
	//dai
	//3dai2 or 3dai1
	for(ll i=2;i<=14;i++){
		if(map[i]==3){
			map[i]-=3;
			for(ll j=2;j<=15;j++){//dai1
				if(map[j]>0&&i!=j){
					map[j]--;
					srh(k+1);
					map[j]++;
				}
			}
			for(ll j=2;j<=14;j++){//dai2
				if(map[j]>1&&i!=j){
					map[j]-=2;
					srh(k+1);
					map[j]+=2;
				}
			}
			map[i]+=3;
		}
	}
	//4dai2 (3daix is also ok)
	for(ll i=2;i<=14;i++){
		if(map[i]>=4){
			//3daix
			map[i]-=3;
			for(ll j=2;j<=15;j++){//dai1
				if(map[j]>0&&i!=j){
					map[j]--;
					srh(k+1);
					map[j]++;
				}
			}
			for(ll j=2;j<=14;j++){//dai2
				if(map[j]>1&&i!=j){
					map[j]-=2;
					srh(k+1);
					map[j]+=2;
				}
			}
			map[i]+=3;
			//4dai2
			map[i]-=4;
			for(ll j=2;j<=15;j++){//dai2 single
				if(map[j]>=1&&i!=j){
					map[j]--;
					for(ll kk=2;kk<=15;kk++){
						if(map[kk]>=1){
							map[kk]--;
							srh(k+1);
							map[kk]++;
						}
					}
					map[j]++;
				}
			}
			for(ll j=2;j<=14;j++){//dai2 double
				if(map[j]>=2&&i!=j){
					map[j]-=2;
					for(ll kk=2;kk<=14;kk++){
						if(map[kk]>=2){
							map[kk]-=2;
							srh(k+1);
							map[kk]+=2;
						}
					}
					map[j]+=2;
				}
			}
			map[i]+=4;
		}
	}
	for(ll i=2;i<=15;i++)
		if(map[i]>0)
			k++;
	ans=min(ans,k);
}
int main(){
	read(T),read(n);
	while(T--){
		ans=100000000;
		pii pai[1005];
		memset(map,0,sizeof map);
		for(ll i=1;i<=n;i++){
			read(pai[i].x),read(pai[i].y);
			if(pai[i].x==1)
				map[14]++;
			else if(pai[i].x==0&&pai[i].y==1)
				map[15]++;
			else if(pai[i].x==0&&pai[i].y==2)
				map[15]++;
			else
				map[pai[i].x]++;
		}
		srh(0);
		print(ans);
		cout<<endl;
	}
	return 0;
}

TLE88pts，on #27 #29 #39 #40 #43 #44