1

7

0 0 2 2 1

0 2 1 6 2

2 0 4 2 1

1 2 4 4 2

1 4 3 6 1

4 0 6 4 1

3 4 6 6 2

#include<stdio.h>

#include<stdlib.h>

int data[100][100] = {0};

int zuo[16][5];

int z = 0;

int x = 0;

int y = 0;

int min = 15;

int cun[16] = {0};

int ip[15] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14};

int op[15];

int num = 0;

void DFS(int col,int step);

bool issafe(int c);

bool safe(int step,int i);

int main()

{

	int n;

	freopen("a.txt","r",stdin);

	scanf("%d",&n);

	for(int t = 0;t < n;t++)

	{

		scanf("%d",&z);

		for(int r = 0;r < z;r++)

		{

			for(int s = 0;s < 5;s++)

			{

				scanf("%d",&zuo[r][s]);

				if(zuo[r][2] > x)

				{

					x = zuo[r][2];

				}

				if(zuo[r][3] > y)

				{

					y = zuo[r][3];

				}

			}

		}

		DFS(0,0);

		printf("%d\n",min);

		num = 0;

		min = 15;

		for(int f = 0;f < 17;f++)

		{

			op[f] = 0;

			cun[f] = 0;

			for(int l = 0;l < 6;l++)

			{

				zuo[f][l] = 0;

			}

		}

		for(int p = 0;p <= x;p++)

		{

			for(int q = 0;q <= y;q++)

			{

				data[p][q] = 0;

			}

		}

	}

	return 0;

}

void DFS(int col,int step)

{

	if(step == z)

	{

		if(num < min)

		{

			min = num;

		}

		return;

	}

	for(int i = 0;i < z;i++)

	{

		if(safe(step,i) && cun[i] == 0 && issafe(i))

		{

			cun[i] = 1;

			op[step] = i;

			for(int a = zuo[i][0];a < zuo[i][2];a++)

			{

				for(int b = zuo[i][1];b < zuo[i][3];b++)

				{

					data[a][b] = zuo[i][4];

				}

			}

			if(col != zuo[i][4])

			{

				num++;

			}

			DFS(zuo[i][4],step + 1);

			cun[i] = 0;

			op[step] = 0;

			for(int a = zuo[i][0];a < zuo[i][2];a++)

			{

				for(int b = zuo[i][1];b < zuo[i][3];b++)

				{

					data[a][b] = 0;

				}

			}

			if(col != zuo[i][4])

			{

				num--;

			}

		}

	}

}

bool issafe(int c)

{

	bool ret = true;

	for(int i = 0;i < zuo[c][0];i++)

	{

		for(int j = zuo[c][1];j < zuo[c][3];j++)

		{

			if(data[i][j] == 0)

			{

				ret = false;

				return ret;

			}

		}

	}

	return ret;

}

bool safe(int step,int i)

{

	bool ret = true;

	for(int k = 0;k < step;k++)

	{

		if(i == op[k])

		{

			ret = false;

			break;

		}

	}

	return ret;

}