#include <stdlib.h>
#include <stdio.h>

struct bunka {
	int lh;
	int ph;
	int l;
	int p;
	int ld;
	int pd;

	int x;
	int y;
};

struct komp {
	int pocet;
	int okna;
};

int N, P, Po, T, C, S, x, y;
int celky;

bool lavyHorny(bunka orig, bunka zist) {
	return (orig.y + 1 == zist.y && orig.x-1 == zist.x);
}

bool pravyHorny(bunka orig, bunka zist) {
	return (orig.y + 1 == zist.y && orig.x == zist.x);
}

bool lavy(bunka orig, bunka zist) {
	return (orig.y == zist.y && orig.x-1 == zist.x);
}

bool pravy(bunka orig, bunka zist) {
	return (orig.y  == zist.y && orig.x+1 == zist.x);
}

bool lavyDolny(bunka orig, bunka zist) {
	return (orig.y - 1 == zist.y && orig.x == zist.x);
}

bool pravyDolny(bunka orig, bunka zist) {
	return (orig.y - 1 == zist.y && orig.x+1 == zist.x);
}

int tried(const void* a, const void* b) {
	return ((komp*)b)->okna - ((komp*)a)->okna;
}

struct bunka bunky[1000];
struct komp komplexy[1000];

int main() {
	scanf("%d\n", &N);

	for ( ; N > 0 ; N--) {
		scanf("%d %d\n", &P, &T);

		Po = P;
		celky = 0;

		for (int i = 0; i < 1000; i++) {
			komplexy[i].okna = 0;
			komplexy[i].pocet = 0;
		}

		for (int k = 0; k < T ; k++) {
			scanf("%d %d", &C, &S);

			komplexy[k].pocet = C;

			for (int i = 0; i < 1000; i++) {
				bunky[i].lh = 1;
				bunky[i].ph = 1;
				bunky[i].l = 1;
				bunky[i].p = 1;
				bunky[i].ld = 1;
				bunky[i].pd = 1;

				bunky[i].x = 10000005;
				bunky[i].y = 10000005;
			}

			for (int i = 0; i < S; i++) {
				scanf("%d %d", &x, &y);				
				bunky[i].x = x; bunky[i].y = y;

				for (int j = 0; j < i; j++) {
					if (bunky[j].lh && bunky[i].pd) {
						if (lavyHorny(bunky[j], bunky[i])) {
							bunky[j].lh = 0;
							bunky[i].pd = 0;
						}
					}

					if (bunky[j].ph && bunky[i].ld) {
						if (pravyHorny(bunky[j], bunky[i])) {
							bunky[j].ph = 0;
							bunky[i].ld = 0;
						}
					}

					if (bunky[j].l && bunky[i].p) {
						if (lavy(bunky[j], bunky[i])) {
							bunky[j].l = 0;
							bunky[i].p = 0;
						}
					}

					if (bunky[j].p && bunky[i].l) {
						if (pravy(bunky[j], bunky[i])) {
							bunky[j].p = 0;
							bunky[i].l = 0;
						}
					}

					if (bunky[j].ld && bunky[i].ph) {
						if (lavyDolny(bunky[j], bunky[i])) {
							bunky[j].ld = 0;
							bunky[i].ph = 0;
						}
					}

					if (bunky[j].pd && bunky[i].lh) {
						if (pravyDolny(bunky[j], bunky[i])) {
							bunky[j].pd = 0;
							bunky[i].lh = 0;
						}
					}
				}							
			}	
			for (int i = 0; i < S; i++) {
				komplexy[k].okna += (bunky[i].lh + bunky[i].l + bunky[i].ld + bunky[i].p + bunky[i].ph + bunky[i].pd);
			}
		}
/*
		for (int i = 0; i < T; i++) {
			printf("Komplex %d - %d okien.\n", i, komplexy[i].okna);
		}*/

		qsort(komplexy, T, sizeof(komp), tried);
		
		int a = 0;
		while (a < T && P > 0) {
			int b = 0;
			while (b < komplexy[a].pocet && P > 0) {
				P -= komplexy[a].okna;
				if (celky > 0) P += 2;
				b++;
				celky++;
			}
			a++;
		}

		if (P > 0) {
			printf("Kapacita zakladny je pouze %d lidi.\n", Po - P);
		} else {
			printf("Je treba %d celku.\n", celky);
		}
	}
  
	return 0;
}