#include<bits/stdc++.h>
using namespace std;
int T,n,pk[20],ans=INT_MAX,kk;
void dfs(int x){
	//printf("%lld\n",x);
	//first 12345
	int k=0;
	for (int i=3;i<=14;i++){
		if(pk[i]>=1){
			k++;
		}
		if(pk[i]<1){
			if(k>=5){
				for (int j=i-k;j<i;j++)
					pk[j]--;
				dfs(x+1);
				for (int j=i-k;j<i;j++)
					pk[j]++;
				cout<<"k:"<<k<<endl;
			}
			k=0;
		}
		else if(i==14){
			if(k>=5){
				for (int j=i-k+1;j<=i;j++)
					pk[j]--;
				dfs(x+1);
				for (int j=i-k+1;j<=i;j++)
					pk[j]++;
				cout<<"       k:"<<k<<endl;
			}
			k=0;
		}
	}
	k=0;
	//second 112233
	for (int i=3;i<=14;i++){
		if(pk[i]>=2){
			k++;
		}
		if(pk[i]<2){
			if(k>=3){
				for (int j=i-k;j<i;j++)
					pk[j]-=2;
				dfs(x+1);
				for (int j=i-k;j<i;j++)
					pk[j]+=2;
			}
			k=0;
		}
		if(i==14){
			if(k>=5){
				for (int j=i-k+1;j<=i;j++)
					pk[j]-=2;
				dfs(x+1);
				for (int j=i-k+1;j<=i;j++)
					pk[j]+=2;
				cout<<"k:"<<k<<endl;
			}
			k=0;
		}
	}
	k=0;
	//third 111222
	for (int i=3;i<=14;i++){
		if(pk[i]>=3){
			k++;
		}
		if(pk[i]<3){
			if(k>=2){
				for (int j=i-k;j<i;j++)
					pk[j]-=3;
				dfs(x+1);
				for (int j=i-k;j<i;j++)
					pk[j]+=3;
			}
			k=0;
		}
		if(i==14){
			if(k>=5){
				for (int j=i-k+1;j<=i;j++)
					pk[j]-=3;
				dfs(x+1);
				for (int j=i-k+1;j<=i;j++)
					pk[j]+=3;
				//cout<<"k:"<<k<<endl;
			}
			k=0;
		}
	}
	
	//fourth 1112
	for (int i=3;i<=16;i++){
		if(pk[i]>=3){
			for (int j=3;j<=16;j++){
				if(pk[j]>=1 and i!=j){
					pk[i]-=3,pk[j]--;
					dfs(x+1);
					pk[i]+=3,pk[j]++;
				}
			}
		}
	}
	//fifth 11122
	for (int i=3;i<=16;i++){
		if(pk[i]>=3){
			for (int j=3;j<=15;j++){
				if(pk[j]>=2 and i!=j){
					pk[i]-=3,pk[j]-=2;
					dfs(x+1);
					pk[i]+=3,pk[j]+=2;
				}
			}
		}
	}
	//sixth 111122
	for (int i=3;i<=16;i++){
		if(pk[i]>=4){
			for (int j=3;j<=15;j++){
				if(pk[j]>=1 and i!=j){
					for(int k=3;k<=15;k++)
						if(pk[k]>=1 and i!=k and j!=k){
							pk[i]-=4,pk[j]--,pk[k]--;
							dfs(x+1);
							pk[i]+=4,pk[j]++,pk[k]++;
						}
							
				}
			}
		}
	}
	for (int i=3;i<=16;i++){
		if(pk[i]>=4){
			for (int j=3;j<=15;j++){
				if(pk[j]>=2 and i!=j){
					for(int k=3;k<=15;k++)
						if(pk[k]>=2 and i!=k and j!=k){
							pk[i]-=4,pk[j]-=2,pk[k]-=2;
							dfs(x+1);
							pk[i]+=4,pk[j]+=2,pk[k]+=2;
						}
							
				}
			}
		}
	}
	int kk=0;
	for (int i=3;i<=17;i++) 
		if(pk[i]!=0){
			cout<<"pk:"<<i<<endl;
			kk++;
		}
	//for (int i=1;i<=16;i++) cout<<pk[i]<<endl;
	ans=min(ans,kk+x);
	cout<<"kk:"<<kk<<" x:"<<x<<" kk+x:"<<kk+x<<" ans:"<<ans<<endl; 
}
int main(){
	//freopen("game001.txt","r",stdin);
	cin>>T;cin>>n;
	while(T--){
	//	cout<<11111<<endl;
		//memset(pk,0,sizeof pk);
		ans=INT_MAX;
		
		for (int i=1;i<=n;i++){
			int a,b;
			cin>>a>>b;
			if((a==0 and b==1)||(a==0 and b==2)) pk[16]++;
			else if(a==2) pk[15]++;
			else if(a==1) pk[14]++;
			else pk[a]++;
		}
		dfs(0);
		for (int i=1;i<=16;i++) cout<<pk[i]<<endl;
		cout<<ans<<endl;
	}
	return 0;
}