Untitled

#include <iostream>
#define N 101
#define oo 2000000
using namespace std;
int ans;
int n;
int sx[N*N],sy[N*N];
int sxx[N*N],syy[N*N];

int dd[N][N];
int d[N][N];
int a[N][N];
int b[N][N];
int hx[]={0,-1,0,1};
int hy[]={-1,0,1,0};
void doc()
{
	ans=0;
	int u,v;
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			{
				cin>>a[i][j];
				dd[i][j]=0;
				b[i][j]=a[i][j];
			}

}
int cnt[6];
int mau( int dau, int cuoi)
{
	for(int i=1;i<=5;i++)cnt[i]=cuoi-dau+1;
	
	while(dau<=cuoi)
	{
		int u=sxx[dau];
		int v=syy[dau];
		dau++;
		for(int i=0;i<4;i++)
		{
			int x=u+hx[i];
			int y=v+hy[i];
			if(x>0&&x<=n&&y>0&&y<=n&&d[x][y]==0)
			{
				if(a[u][v]==0)
					{
					cnt[a[x][y]]++;
					d[x][y]=1;
					sxx[++cuoi]=x;
					syy[cuoi]=y;
					}else if(a[u][v]==a[x][y])
						{
						cnt[a[x][y]]++;
						d[x][y]=1;
						sxx[++cuoi]=x;
						syy[cuoi]=y;
						}
			}
		}
	}
	int kq=0;
	for(int i=1;i<=5;i++)
	{
		if(cnt[i]>=cnt[kq])kq=i;
	}
	return kq;
}

void xuli(int tx, int ty)
{
	int dau=1,cuoi=0;
	sxx[++cuoi]=tx;
	syy[cuoi]=ty;
	dd[tx][ty]=1;
	while(dau<=cuoi)
	{
		int u=sxx[dau];
		int v=syy[dau];
		dau++;
		for(int i=0;i<4;i++)
		{
			int x=u+hx[i];
			int y=v+hy[i];
			if(x>0&&x<=n&&y>0&&y<=n&&b[x][y]==b[tx][ty]&&dd[x][y]==0)
			{
				dd[x][y]=1;
				sxx[++cuoi]=x;
				syy[cuoi]=y;
			}
		}
	}
}

void bfs(int tx,int ty)
{
	
	int dau=1,cuoi=0;
	sx[++cuoi]=tx;
	sy[cuoi]=ty;
	dd[tx][ty]=1;
	while(dau<=cuoi)
	{
		int u=sx[dau];
		int v=sy[dau];
		//cout<<u<<" "<<v<<"\n";
		dau++;
		for(int i=0;i<4;i++)
		{
			int x=u+hx[i];
			int y=v+hy[i];
			if(x>0&&x<=n&&y>0&&y<=n&&a[x][y]==0&&dd[x][y]==0)
			{
				dd[x][y]=1;
				sx[++cuoi]=x;
				sy[cuoi]=y;
			}
		}
	}
	//<<"\n";
	
		for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)d[i][j]=0;
		for(int i=1;i<=cuoi;i++)
			{
				d[sx[i]][sy[i]]=1;
				sxx[i]=sx[i];
				syy[i]=sy[i];
			}

		int color=mau(1,cuoi);
	for(int i=1;i<=cuoi;i++)b[sx[i]][sy[i]]=color,a[sx[i]][sy[i]]=0;

}

int main()
{
	//freopen("input.txt","r",stdin);
	int TC;
	
	cin>>TC;
	for(int tc=1;tc<=TC;tc++)
	{
		doc();
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)if(b[i][j]==0)bfs(i,j);

		for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)dd[i][j]=0;

		for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)if(dd[i][j]==0)
			{
				xuli(i,j);
				ans++;
			}
			

		cout<<"Case #"<<tc<<"\n";
		
		cout<<ans<<"\n";
	}
	return 0;
}