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

int main() {
	int T;
	cin >> T;
	for(int t =0; t < T; t++) {
		int C,N;
		cin >> C >> N;
		vector< pair<int,int> > A(N);
		int dx[] ={1,-1,0,0,1,-1};
		int dy[] ={0,0,1,-1,-1,1};
		int s =0;
		for(int i =0; i < N; i++) {
			int K;
			cin >> A[i].second >> K;
			s +=A[i].second;
			set< pair<int,int> > S;
			A[i].first =6*K-2;
			for(int j =0; j < K; j++) {
				int x,y;
				cin >> x >> y;
				for(int k =0; k < 6; k++)
					if(S.find(make_pair(x+dx[k],y+dy[k])) != S.end()) A[i].first -=2;
				S.insert(make_pair(x,y));}
			}
		sort(A.begin(),A.end());
		int ans =0, C0 =C;
		if(s > 0) C -=2;
		for(int i =N-1; i >= 0; i--) {
			if(1LL*A[i].second*A[i].first < 1LL*C) {
				C -=A[i].second*A[i].first; 
				ans +=A[i].second; 
				continue;}
			ans +=C/A[i].first;
			C %=A[i].first;
			if(C > 0) ans++;
			C =-1;
			break;}
		if(C > 0) cout << "Kapacita zakladny je pouze " << C0-C << " lidi.\n";
		else cout << "Je treba " << ans << " celku.\n";}
	}