000

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define re register
#define ri register int
#define rll register long long
#define ld long double
#define endl '\n'
#define fi first
#define se second
#define pii pair<int,int>
#define p_q priority_queue
#define iter iterator
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define nep(i,a,b) for(int i=(a);i<=(b);i--)
#define popcount __builtin_popcount
int t,n,cnt[114],minn,yhb=0;
void dfs(int c,int k){
yhb++;
if(yhb>=600001) return ;
if(c>=minn) return ;
int cn=0;
for(int i=3;i<=14;i++){
if(i14) i=1;
if(cnt[i]<3) cn=0;
else cn++;
if(cn>=2){
if(i1) i=14;
for(int j=i-cn+1;j<=i;j++){
if(j!=14) cnt[j]-=3;
else cnt[1]-=3;
}
dfs(c+1,k+1);
for(int j=i-cn+1;j<=i;j++){
if(j!=14) cnt[j]+=3;
else cnt[1]+=3;
}
if(i14) i=1;
}
if(i1) break;
}
cn=0;
for(int i=3;i<=14;i++){
if(i14) i=1;
if(cnt[i]<2) cn=0;
else cn++;
if(cn>=3){
if(i1) i=14;
for(int j=i-cn+1;j<=i;j++){
if(j!=14) cnt[j]-=2;
else cnt[1]-=2;
}
dfs(c+1,k+1);
for(int j=i-cn+1;j<=i;j++){
if(j!=14) cnt[j]+=2;
else cnt[1]+=2;
}
if(i14) i=1;
}
if(i1) break;
}
cn=0;
for(int i=3;i<=14;i++){
if(i14) i=1;
if(0cnt[i]) cn=0;
else cn++;
if(cn>=5){
if(i1) i=14;
for(int j=i-cn+1;j<=i;j++){
if(j!=14) cnt[j]--;
else cnt[1]--;
}
dfs(c+1,k+1);
for(int j=i-cn+1;j<=i;j++){
if(j!=14) cnt[j];
else cnt[1];
}
if(i14) i=1;
}
if(i1) break;
}
for(int i=1;i<=13;i++){
if(cnt[i]>=4){
cnt[i]-=4;
for(int j=1;j<=15;j++){
for(int k=1;k<=15;k++){
if(cnt[j]>=2&&cnt[k]>=2&&j<=13&&k<=13){
cnt[j]-=2;
cnt[k]-=2;
dfs(c+1,k+1);
cnt[j]+=2;
cnt[k]+=2;
}
if(cnt[j]&&cnt[k]){
cnt[j]--;
cnt[k]--;
dfs(c+1,k+1);
cnt[j];
cnt[k];
}
}
}
cnt[i]+=4;
}
}
for(int i=1;i<=13;i++){
if(cnt[i]>=3){
cnt[i]-=3;
for(int j=1;j<=15;j++){
if(cnt[j]>=2&&j<=13){
cnt[j]-=2;
dfs(c+1,k+1);
cnt[j]+=2;
}else if(cnt[j]){
cnt[j]--;
dfs(c+1,k+1);
cnt[j];
}
}
cnt[i]+=3;
}
}
for(int i=1;i<=13;i){
if(cnt[i]4){
cnt[i]-=4;
dfs(c+1,k+1);
cnt[i]+=4;
}else if(cnt[i]3){
cnt[i]-=3;
dfs(c+1,k+1);
cnt[i]+=3;
}else if(cnt[i]2){
cnt[i]-=2;
dfs(c+1,k+1);
cnt[i]+=2;
}
}
if(cnt[14]&&cnt[15]){
cnt[14]=0;
cnt[15]=0;
dfs(c+1,k+1);
cnt[14]=1;
cnt[15]=1;
}
int cc=c;
for(int i=1;i<=15;i++){
if(cnt[i]){
cc++;
}
}
minn=min(minn,cc);
}
int main(){
cin>>t>>n;
while(t--){
memset(cnt,0,sizeof(cnt));
yhb=0;
for(int i=1;i<=n;i++){
int a,b;
scanf("%d%d",&a,&b);
if(a0&&b1) cnt[14]++;
else if(a0&&b2) cnt[15];
else cnt[a];
}
minn=n;
dfs(0,0);
cout<<minn<<'\n';
}
return 0;
}