#include <bits/stdc++.h>
using namespace std;

int num[100], dp[30][30][30][30], cnt[100];
int n, t, ans;

void Dp()
{
	memset(dp, 0x3f, sizeof(dp));
	dp[0][0][0][0] = 0;
	for (int l = 0; l <= 25; l++)
		for (int k = 0; k <= 25; k++)
			for (int j = 0; j <= 25; j++)
				for (int i = 0; i <= 25; i++)
					{
						int minn = 2e9;
						if (i > 0) minn = min(minn, dp[i - 1][j][k][l] + 1);
						// 单张
						if (j > 0) minn = min(minn, dp[i][j - 1][k][l] + 1);
						// 对子
						if (k > 0) minn = min(minn, dp[i][j][k - 1][l] + 1);
						// 三张
						if (l > 0) minn = min(minn, dp[i][j][k][l - 1] + 1);
						// 炸弹
						if (k > 0 && i > 0) minn = min(minn, dp[i - 1][j][k - 1][l] + 1);
						// 三带一
						if (k > 0 && j > 0) minn = min(minn, dp[i][j - 1][k - 1][l] + 1);
						// 三带二
						if (l > 0 && i > 1) minn = min(minn, dp[i - 2][j][k][l - 1] + 1);
						// 四带二单
						if (l > 0 && j > 0) minn = min(minn, dp[i][j - 1][k][l - 1] + 1);
						// 四带二同单
						if (l > 0 && j > 1) minn = min(minn, dp[i][j - 2][k][l - 1] + 1);
						// 四带二对
						if (l > 1) minn = min(minn, dp[i][j][k][l - 2] + 1);
						// 四带二同对
						if (j > 0) minn = min(minn, dp[i + 2][j - 1][k][l]);
						// 拆对子
						if (k > 0) minn = min(minn, dp[i + 1][j + 1][k - 1][l]);
						// 拆三张 -> 单张+对子
						if (l > 0) minn = min(minn, dp[i + 1][j][k + 1][l]);
						// 拆炸弹 -> 单张+三张
						if (l > 0) minn = min(minn, dp[i][j + 2][k][l - 1]);
						// 拆炸弹 -> 二对子
						dp[i][j][k][l] = min(minn, dp[i][j][k][l]);
					}
}

void dfs(int step)
{
	if (step >= ans) return ;
	cnt[1] = cnt[2] = cnt[3] = cnt[4] = cnt[5] = 0;
	for (int i = 2; i <= 14; i++) cnt[num[i]]++;
	cnt[5] = num[1];
	ans = min(ans, step + dp[cnt[1] + num[1]][cnt[2]][cnt[3]][cnt[4]]);
	if (num[1] >= 2) ans = min(ans, step + dp[cnt[1]][cnt[2]][cnt[3]][cnt[4]] + 1);
	for (int i = 1; i <= 3; i++)
		for (int j = 3; j <= 14; j++)
			for (int k = 4 / i + 1; j + k <= 15; k++)
			{
				bool flag = false;
				for (int l = j; l <= j + k - 1; l++)
					if (num[l] < i) flag = true;
				if (flag) continue;
				for (int l = j; l <= j + k - 1; l++)
					num[l] -= i;
				dfs(step + 1);
				for (int l = j; l <= j + k - 1; l++)
					num[l] += i;
			}
}

int main()
{
	ios::sync_with_stdio(false);
	cin >> t >> n;
	Dp();
	while (t--)
	{
		memset(num, 0, sizeof(num));
		ans = n;
		for (int i = 1; i <= n; i++)
		{
			int point, c;
			cin >> point >> c;
			num[point]++;
		}
		num[14] = num[1];
		num[1] = num[0];
		dfs(0);
		cout << ans << endl;
	}
	return 0;
}