Untitled

#include <iostream>
using namespace std;
int a[100][100];
int save[100][100];
int vis[100][100];
int vis1[100][100];
int dem[6];
int n;
int qx[10000000];
int qy[10000000];
int qd[10000000];
int f;
int r;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
void push(int x,int y){
	r++;
	qx[r]=x;
	qy[r]=y;
//qd[r]=z;
}
void pop(int &x,int &y){
	f++;
	x=qx[f];
	y=qy[f];
	//dis=qd[f];
}
void check(){
	
	int x,y;
	int flag=0;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(a[i][j]==0&&vis[i][j]==0){
				for(int i=1; i<=5;i++){
					dem[i]=0;
				}
				flag++;
				f=r=-1;
				x=i;
				y=j;
				push(x,y);
				vis[x][y]=flag;
	while(f!=r){
		pop(x,y);
		for(int i=0;i<4; i++){
			int xx=x+dx[i];
			int yy=y+dy[i];
			if(xx>=0&&xx<n&&yy>=0&&yy<n){
				if(a[x][y]==0){
					if(a[xx][yy]==0&&vis[xx][yy]!=flag) {
						push(xx,yy);
						vis[xx][yy]=flag;
					}
					else if(vis[xx][yy]!=flag&&save[xx][yy]!=0){
						push(xx,yy);
						vis[xx][yy]=flag;
						dem[a[xx][yy]]++;
					}
				}
				else{
					if(a[xx][yy]==a[x][y]&&vis[xx][yy]!=flag&&save[xx][yy]!=0){
						push(xx,yy);
						vis[xx][yy]=flag;
						dem[a[xx][yy]]++;
					}
				}
			}
		}
	}
	int max=0;
		for(int i=1; i<6; i++){
			if(max<dem[i]) max=dem[i];
		}
		int doi;
		for(int i=1; i<6; i++){
			if(max==dem[i]) doi=i;
		}
		for(int i=0;i<n;i++){
			for(int j=0; j<n;j++){
				if(a[i][j]==0&&vis[i][j]==flag) a[i][j]=doi;
			}
		}
			}
		}
	}
}
int demvung(){
	
	int dem=0;
	for(int i=0;i<n; i++){
		for(int j=0; j<n;j++){
			if(vis1[i][j]==0){
				dem++;
				f=r=-1;
				int x=i;
				int y=j;
				vis[x][y]=1;
				push(x,y);
				while(f!=r){
					pop(x,y);
					for(int i=0; i<4; i++){
						int xx=x+dx[i];
						int yy=y+dy[i];
						if(xx>=0&&xx<n&&yy>=0&&yy<n){
							if(a[xx][yy]==a[x][y]&&vis1[xx][yy]==0){
								push(xx,yy);
								vis1[xx][yy]=1;
							}
						}
					}
				}
			}
		}
	}
	return dem;
}

int main(){
//freopen("input.txt","r",stdin);
	int t;
	cin>>t;
	for (int tc=1; tc<=t;tc++){
		cout<<"Case #"<<tc<<endl;
		cin>>n;
		for(int i=0;i<n;i++){
			for(int j=0; j<n;j++){
				cin>>a[i][j];
				save[i][j]=a[i][j];
				vis[i][j]=0;
				vis1[i][j]=0;
			}
		}
		
		check();
		int kq=demvung();
		cout<<kq<<endl;
	}
	return 0;
}