#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>

using namespace std;

#define REP(i, N) for(int (i)=0; (i)<(N); (i)++)
#define ll long long
#define mp make_pair
#define pb push_back
vector< pair<int,int> > Si[1111];
pair<int, int> bloky[1111];
int d[6][2] = {
	{1,0}, {0,1},{-1, 0},{0,-1},
	{1,-1},{-1,1}
};

int main() {
	int Tests;
	scanf("%d", &Tests);
	REP(TTTT, Tests) {
		int P, T;
		scanf("%d %d", &P, &T);
		REP(i, T) {
			int C,S;
			scanf("%d%d", &C, &S);
			bloky[i].first = 6*S;
			bloky[i].second = C;
			map< pair<int, int>,bool > inBlock;
			vector< pair<int, int> > SS;
			int sub = 0;
			REP(j, S) {
				int x,y;
				scanf("%d%d", &x, &y);
				SS.pb(mp(x,y));
				inBlock[mp(x,y)] = 1;
			}
			REP(j, SS.size()) {
				REP(dir, 6) {
					int xx = SS[j].first+d[dir][0], yy = SS[j].second+d[dir][1];
					if(inBlock.find(mp(xx, yy)) != inBlock.end()) sub++;
				}
			}
			bloky[i].first -= sub;
		//	printf("blok i: %d %d\n", bloky[i].first, bloky[i].second);
		}
		sort(bloky, bloky+T);
		int sum = 2;
		int x = 0;

		for(int i = T-1; i >= 0; i--) {
			REP(j, bloky[i].second) {
				sum += bloky[i].first-2;
//				printf("csum: %d\n", sum);
				x++;
				if(sum >= P) {
					printf("Je treba %d celku.\n", x);
					i = -1;
					break;
				}
			}
		}
		if(sum < P || x == 0) {
			if(x == 0) sum -= 2;
			printf("Kapacita zakladny je pouze %d lidi.\n", sum);
		}
	}

	return 0;
}