#include <bits/stdc++.h>
using namespace std;
const int N = 100 + 5;
int t , n , x , y , a[N] , deep;
bool check()
{
	for(int i = 3 ; i <= 17 ; ++ i )
	{
		if(a[i] > 0) return 0;	
	}	
	return 1;
} 
bool dfs(int x)
{
	if(x == deep + 1) return check();
	// 四带二(两双)
		for(int i = 3 ; i <= 17 ; ++ i )
	{
		for(int j = 3 ; j <= 17 ; ++ j )
		{
			for(int k = 3 ; k <= 17; ++k )
			{
				if(i != j && j != k && i != k)
				{
					if(a[i] >= 4 && a[j] >= 2 && a[k] >= 2)
					{
						a[i] -= 4;
						a[j] -= 2;
						a[k] -= 2;
						if(dfs(x + 1)) return 1;
						a[i] += 4;
						a[j] += 2;
						a[k] += 2;
					}
				}
			}
		}
	} 
	// 四带二(两单)
	for(int i = 3 ; i <= 17 ; ++ i )
	{
		for(int j = 3 ; j <= 17 ; ++ j )
		{
			for(int k = 3 ; k <= 17; ++k )
			{
				if(i != j && j != k && i != k)
				{
					if(a[i] >= 4 && a[j] >= 1 && a[k] >= 1)
					{
						a[i] -= 4;
						-- a[j];
						-- a[k];
						if(dfs(x + 1)) return 1;
						a[i] += 4;
						++ a[j];
						++ a[k];
					}
				}
			}
		}
	} 
	
		// 三顺
	for(int i = 3 ; i <= 13 ; ++ i ) 
	{
		for(int j = 2 ; i + j - 1 <= 14 ; ++ j )
		{
			bool opt = 0;
			for(int k = i ; k <= i + j - 1 ; ++ k )
			{
				if(a[k] <= 2) 
				{
					opt = 1;
					break;
				}	
			}	
			if(!opt)
			{
				for(int k = i ; k <= i + j - 1 ; ++ k ) a[k] -= 3;		
				if(dfs(x + 1)) return 1;
				for(int k = i ; k <= i + j - 1 ; ++ k ) a[k] += 3;
			}
		}	
	} 
		// 双顺 
	for(int i = 3 ; i <= 12 ; ++ i ) 
	{
		for(int j = 3 ; i + j - 1 <= 14 ; ++ j )
		{
			bool opt = 0;
			for(int k = i ; k <= i + j - 1 ; ++ k )
			{
				if(a[k] <= 1) 
				{
					opt = 1;
					break;
				}	
			}	
			if(!opt)
			{
				for(int k = i ; k <= i + j - 1 ; ++ k ) a[k] -= 2;		
				if(dfs(x + 1)) return 1;
				for(int k = i ; k <= i + j - 1 ; ++ k ) a[k] += 2;
			}
		}	
	} 
		// 单顺
	for(int i = 3 ; i <= 10 ; ++ i ) // 10 j q k a
	{
		for(int j = 5 ; i + j - 1 <= 14 ; ++ j )
		{
			bool opt = 0;
			for(int k = i ; k <= i + j - 1 ; ++ k )
			{
				if(!a[k]) 
				{
					opt = 1;
					break;
				}	
			}	
			if(!opt)
			{
				for(int k = i ; k <= i + j - 1 ; ++ k ) -- a[k];				
				if(dfs(x + 1)) return 1;
				for(int k = i ; k <= i + j - 1 ; ++ k ) ++ a[k];				
			}
		}	
	} 
		// 三带二
	for(int i = 3 ; i <= 17 ; ++ i )
	{
		for(int j = 3 ; j <= 17 ; ++ j)
		{
			if(i != j)
			{
				if(a[i] >= 3 && a[j] >= 2)
				{
					a[i] -= 3;
					a[j] -= 2;
					if(dfs(x + 1)) return 1;
					a[i] += 3;
					a[j] += 2;	
				}	
			}	
		}
	} 
		// 三带一
	for(int i = 3 ; i <= 17 ; ++ i )
	{
		for(int j = 3 ; j <= 17 ; ++ j )
		{
			if(i != j)
			{
				if(a[i] >= 3 && a[j] >= 1)	
				{
					a[i] -= 3;
					-- a[j];
					if(dfs(x + 1)) return 1;
					a[i] += 3;
					++ a[j];
				}
			}	
		}	
	} 
	// 火箭
	if(a[16] >= 1 && a[17] >= 1)
	{
		-- a[16];
		-- a[17];
		dfs(x + 1);
		++ a[16];
		++ a[17];
	}
		// 四发
	for(int i = 3 ; i <= 17 ; ++ i )
	{
		if(a[i] >= 4)
		{
			a[i] -= 4;
			if(dfs(x + 1)) return 1;
			a[i] += 4; 
		}
	}
		// 三发
	for(int i = 3 ; i <= 17 ; ++ i )
	{
		if(a[i] >= 3)
		{
			a[i] -= 3;
			if(dfs(x + 1)) return 1;
			a[i] += 3;
		}
	} 
		// 双发
	for(int i = 3 ; i <= 17 ;  ++ i )
	{
		if(a[i] >= 2)
		{
			a[i] -= 2;
			if(dfs(x + 1)) return 1;
			a[i] += 2;
		}
	} 	
	// 单发
	for(int i = 3 ; i <= 17 ; ++ i )
	{
		if(a[i] >= 1)
		{
			-- a[i];
			if(dfs(x + 1)) return 1;
			++ a[i];
		}
	} 
	return 0;
}
int main()
{
//	freopen("landlords.in" , "r" , stdin);
//	freopen("landlords.out" , "w" , stdout);
	cin >> t >> n ; 
	while(t--)
	{
		memset(a , 0 , sizeof(a));
		for(int i = 1 ; i <= n ; ++ i )
		{
			cin >>x >> y ;
			if(x == 1) x = 14;
			else if(x == 2) x = 15;
			else if(x == 0 && y == 1) x = 16;
			else if(x == 0 && y == 2) x = 17;
			++a[x];
		}	
		deep = 0;
		while(!dfs(1)) ++ deep;	
		cout << deep << endl;
	}
	return 0;
}

tle30如何优化