#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,a[100],mi;
void dfs(int x)
{
	if(x>mi) return;
	int p=0;
	for(int i=3;i<=14;i++)
	{
		if(a[i]==0) p=0;
		else
		{
			p++;
			if(p>=5)
			{
				for(int j=i-p+1;j<=i;j++) a[j]--;
				dfs(x+1);
				for(int j=i-p+1;j<=i;j++) a[j]++;
			}
		}
	}
	p=0;
	for(int i=3;i<=14;i++)
	{
		if(a[i]<2) p=0;
		else
		{
			p++;
			if(p>=3)
			{
				for(int j=i-p+1;j<=i;j++) a[j]-=2;
				dfs(x+1);
				for(int j=i-p+1;j<=i;j++) a[j]+=2;
			}
		}
	}
	p=0;
	for(int i=3;i<=14;i++)
	{
		if(a[i]<3) p=0;
		else
		{
			p++;
			if(p>=2)
			{
				for(int j=i-p+1;j<=i;j++) a[j]-=3;
				dfs(x+1);
				for(int j=i-p+1;j<=i;j++) a[j]+=3;
			}
		}
	}
	for(int i=2;i<=14;i++)
	{
		if(a[i]==3)
		{
			a[i]-=3;
			for(int j=0;j<=14;j++)
			{
				if(a[j]==0||i==j) continue;
				a[j]--;
				dfs(x+1);
				a[j]++;
			}
			for(int j=1;j<=14;j++)
			{
				if(a[j]<2||i==j) continue;
				a[j]-=2;
				dfs(x+1);
				a[j]+=2;
			}
			a[i]+=3;
		}
		if(a[i]==4)
		{
			a[i]-=3;
			for(int j=0;j<=14;j++)
			{
				if(a[j]==0||i==j) continue;
				a[j]--;
				dfs(x+1);
				a[j]++;
			}
			for(int j=2;j<=14;j++)
			{
				if(a[j]<2||i==j) continue;
				a[j]-=2;
				dfs(x+1);
				a[j]+=2;
			}
			a[i]+=3;
			a[i]-=4;
			for(int j=0;j<=14;j++)
			{
				if(a[j]<=0||i==j) continue;
				a[j]--;
				for(int k=0;k<=14;k++)
				{
					if(a[k]<=0||j==k) continue;
					a[k]--;
					dfs(x+1);
					a[k]++;
				}
				a[j]++;
			}
			for(int j=2;j<=14;j++)
			{
				if(a[j]<2||i==j) continue;
				a[j]-=2;
				for(int k=0;k<=14;k++)
				{
					if(a[k]<=2||j==k) continue;
					a[k]-2;
					dfs(x+1);
					a[k]+=2;
				}
				a[j]+=2;
			}
			a[i]+=4;
		}
	}
	for(int i=0;i<=14;i++)
	{
		if(a[i]) x++;
	}
	mi=min(mi,x);
}
int main()
{
	cin>>n>>m;
	while(n--)
	{
		mi=21e8;
		for(int i=1;i<=m;i++)
		{
			cin>>x>>y;
			if(x==1) a[14]++;
			else a[x]++;
		}
		dfs(0);
		cout<<mi<<endl;
	}
	return 0;
}