#include <cstdio>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <cstring>
#include <cmath>
#include <deque>
#include <iostream>
#include <algorithm>

typedef long long int lint;




using namespace std;

int dx[] = {1,0,-1,0,1,-1};
int dy[] = {0,1,0,-1,-1,1};

int main()
{
	int N; scanf("%d", &N);
	for (int n = 0; n < N; ++n)
	{
		int cs[1111];
		int cc[1111];
		int cp[1111];
		vector<int> cap;
		int P, T; scanf("%d %d", &P, &T);
		for (int t = 0; t < T; ++t)
		{
			set<pair<int, int> > centers;
			set<pair<pair<int, int>, pair<int, int> > > edges;
			scanf("%d %d", &cs[t], &cc[t]);
			for (int c = 0; c < cc[t]; ++c)
			{
				int x, y; scanf("%d %d", &x, &y);
				centers.insert(make_pair(x, y));
			}
			for (set<pair<int, int> >::iterator it = centers.begin(); it != centers.end(); ++it)
			{
				int x = it->first;
				int y = it->second;
				for (int i = 0; i < 6; ++i)
				{
					pair<int, int> p2 = make_pair(x + dx[i], y + dy[i]);
					if (centers.find(p2) != centers.end())
					{
						edges.insert(make_pair(*it, p2));
						edges.insert(make_pair(p2, *it));
					}
				}
			}
			cp[t] = 6 * cc[t] - edges.size();
			for (int s = 0; s < cs[t]; ++s)
			{
				cap.push_back(cp[t]);
			}
		}
		sort(cap.begin(), cap.end(), greater<int>());
		int rem = P;
		int res = 0;
		for (int i = 0; i < cap.size(); ++i)
		{
			if (rem <= 0)
			{
				res = i;
				break;
			}
			rem -= cap[i];
			if (i) rem += 2;
		}
		if (rem <= 0)
		{
			printf("Je treba %d celku.\n",  res);
		}
		else
		{
		    printf("Kapacita zakladny je pouze %d lidi.\n", P - rem);
		}

		
	}
}