#include<bits/stdc++.h>

using namespace std;

int p[20];

int T,n,cnt=0,ans=0x3f3f3f3f;
	
int hs,sz;

int sum=0;

void dfs(int cnt,int sum){
	
	if(cnt<0) return;
	
	if(sum>ans) return;
	
	//打完 
	
	if(cnt==0){
		ans=min(ans,sum);
		cout<<ans<<endl;
		return;
	}
	
	
	if(p[0]==2){
		p[0]=0;
		dfs(cnt-2,sum++);
		p[0]=2;
	}
	
	for(int i=0;i<14;i++){
		if(p[i]>=4){
			p[i]-=4;
			if(cnt-4<0) ;
			else dfs(cnt-4,sum+1);
			p[i]+=4;
		}
	}
	
	//4带2
	
	for(int i=1;i<14;i++){
		if(p[i]>=4){
			p[i]-=4;
			for(int j=0;j<14;j++){
				if(p[j]>=1){
					p[j]-=1;
					for(int ee=0;ee<14;ee++){
						if(p[ee]>=1){
							
							p[ee]-=1;
							if(cnt-6<0) ;
							else dfs(cnt-6,sum+1);
							p[ee]+=1;
						}
					}
					p[j]+=1;
				} 
			}
			p[i]+=4;
		}
	}
	
	//3带2 
	
	for(int i=1;i<14;i++){
		if(p[i]>=3){
			p[i]-=3;
			for(int j=1;j<14;j++){
				if(p[j]>=2){
					
					p[j]-=2;
					if(cnt-5<0) ;
					else dfs(cnt-5,sum+1);
					p[j]+=2;
				} 
			}
			p[i]+=3;
		}
	}
	
	//3带1
	
	for(int i=1;i<14;i++){
		if(p[i]>=3){
			p[i]-=3;
			for(int j=0;j<14;j++){
				if(p[j]>=1){
					
					p[j]-=1;
					if(cnt-4<0) ;
					else dfs(cnt-4,sum+1);
					p[j]+=1;
				} 
			}
			p[i]+=3;
		}
	}
	
	//顺子
	
	for(int i=3;i<14;i++){
		int pz=0;
		for(int j=i;j<14;j++){
			if(p[j]>=1) pz++;
			else{
				if(pz>=5){
					for(int r=0;r<=pz-5;r++){
						for(int ee=j;ee<=pz-r;ee++){
							p[ee]--;
						}
						if(cnt-pz+r<0) ;
						else dfs(cnt-pz+r,sum+1);
						for(int ee=j;ee<=pz-r;ee++){
							p[ee]++;
						}
					}
					pz=0;
					break;
				}
				else{
					pz=0;
					break;
				}
			} 
		} 
	}
	
	
	//2顺子
	
	for(int i=3;i<14;i++){
		int pz=0;
		for(int j=i;j<14;j++){
			if(p[j]>=2) pz++;
			else{
				if(pz>=3){
					for(int r=3;r<=pz-3;r++){
						for(int ee=j;ee<=pz-r;ee++){
							p[ee]-=2;
						}
						if(cnt-pz+r<0) ;
						else dfs(cnt-pz+r,sum+1);
						for(int ee=j;ee<=pz-r;ee++){
							p[ee]+=2;
						}
					}
					pz=0;
					break;
				}
				else{
					pz=0;
					break;
				}
			} 
		} 
	}
	
	
	//3顺子
	 
	 
	for(int i=3;i<14;i++){
		int pz=0;
		for(int j=i;j<14;j++){
			if(p[j]>=2) pz++;
			else{
				if(pz>=3){
					for(int r=3;r<=pz-3;r++){
						for(int ee=j;ee<=pz-r;ee++){
							p[ee]-=3;
						}
						if(cnt-pz+r<0) ;
						else dfs(cnt-pz+r,sum+1);
						for(int ee=j;ee<=pz-r;ee++){
							p[ee]+=3;
						}
					}
					pz=0;
					break;
				}
				else{
					pz=0;
					break;
				}
			} 
		} 
	} 
	
	for(int i=1;i<14;i++){
		if(p[i]>=3){
			p[i]-=3;
			if(cnt-3<0) ;
			else dfs(cnt-3,sum+1);
			p[i]+=3;
		}
	}
	
	
	
	for(int i=1;i<14;i++){
		if(p[i]>=2){
			p[i]-=2;
			if(cnt-2<0) ;
			else dfs(cnt-2,sum+1);
			p[i]+=2;
		}
	}
	
	for(int i=0;i<14;i++){
		if(p[i]>=1){
			p[i]--;
			if(cnt-1<0) ;
			else dfs(cnt-1,sum+1);
			p[i]++;
			
		}
	}
}

signed main(){
	
	cin>>T>>n;
	
	while(T--){
		cnt=n;
		
		memset(p,0,sizeof(p));
		
		for(int i=0;i<n;i++){
			cin>>sz>>hs;
			p[sz]++;
		}
		
		sum=0;
		
		dfs(cnt,sum);
		
		cout<<ans<<endl;
		
		ans=0x3f3f3f; 
	}
	
	
}