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

struct POINT
{
	int x;
	int y;
	
	int operator < (const POINT& Point) const
	{
		if(x == Point.x)
		{
			return y < Point.y;
		}
		
		return x < Point.x;
	}
};

using namespace std;
typedef set<POINT> SET;
typedef SET::iterator IT;

#define MAXT 2000



struct BUILDING
{
	int c;
	int n;
	int cap;
	SET Set;
};

struct SHORT_BUILDING
{
	int c;
	int cap;
	
	int operator < (const SHORT_BUILDING& B) const
	{
		return cap < B.cap;
	}
};

BUILDING B[MAXT];
SHORT_BUILDING SB[MAXT];



void CheckPoint(BUILDING& B, const POINT& P)
{
	if(B.Set.find((POINT) {P.x - 1, P.y}) == B.Set.end()) B.cap++;
	if(B.Set.find((POINT) {P.x + 1, P.y}) == B.Set.end()) B.cap++;
	if(B.Set.find((POINT) {P.x, P.y - 1}) == B.Set.end()) B.cap++;
	if(B.Set.find((POINT) {P.x, P.y + 1}) == B.Set.end()) B.cap++;
	if(B.Set.find((POINT) {P.x - 1, P.y + 1}) == B.Set.end()) B.cap++;
	if(B.Set.find((POINT) {P.x + 1, P.y - 1}) == B.Set.end()) B.cap++;
}


void CountWindows(BUILDING& B)
{
	B.cap = 0;
	for(IT it = B.Set.begin(); it != B.Set.end(); it++)
	{
		CheckPoint(B, *it);
	}
}


int main()
{
	int n;
	scanf("%d", &n);
	
	for(int c = 0; c < n; c++)
	{
		int p, t;
		scanf("%d%d", &p, &t);
		
		for(int i = 0; i < t; i++)
		{
			scanf("%d%d", &(B[i].c), &(B[i].n));
			B[i].Set.clear();
			
			for(int j = 0; j < B[i].n; j++)
			{
				int x, y;
				scanf("%d%d", &x, &y);
				
				B[i].Set.insert((POINT) {x, y});
			}
			
			CountWindows(B[i]);
		}
		
		int pOrig = p;
		p -= 2;
		for(int i = 0; i < t; i++)
		{
			SB[i].c = B[i].c;
			SB[i].cap = B[i].cap - 2;
		}
		
		sort(SB, SB + t);
		
		int nUsed = 0, nCur;
		
		for(int i = t - 1; i >= 0; i--)
		{
			//printf("Tyhle mam %d, cap je %d\n", SB[i].c, SB[i].cap);
			
			if((SB[i].c - 1) * SB[i].cap < p)
			{
				nCur = SB[i].c;
			}
			else
			{
				nCur = (p + (SB[i].cap - 1)) / SB[i].cap;
			}
			
			p -= nCur * SB[i].cap;
			nUsed += nCur;
			
			if(p <= 0)
			{
				printf("Je treba %d celku.\n", nUsed);
				goto NEXT_INPUT;
			}
		}
		
		printf("Kapacita zakladny je pouze %d lidi.\n", pOrig - p);
		
		NEXT_INPUT:;
	}
	
	return 0;
}