Untitled

package hugo_dem_vung;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
	static int n, res;
	static int[][] a, visit, vis;
	static int[] dx = { -1, 0, 1, 0 }, dy = { 0, -1, 0, 1 };
	static int[] qx = new int[10000], qy = new int[10000], dientich, ke,
			quex = new int[10000], quey = new int[10000];

	public static boolean checkOut(int x, int y) {
		if (x < 0 || x >= n || y < 0 || y >= n) {
			return false;
		}
		return true;
	}

	public static void BFS(int x, int y, int v) {
		int front = 0, rear = 0;
		qx[front] = x;
		qy[front] = y;
		visit[x][y] = 1;
		while (front <= rear) {
			int xt = qx[front], yt = qy[front];
			for (int i = 0; i < 4; i++) {
				int nx = xt + dx[i], ny = yt + dy[i];
				if (checkOut(nx, ny) && visit[nx][ny] == 0 && a[nx][ny] == v) {
					rear++;
					qx[rear] = nx;
					qy[rear] = ny;
					visit[nx][ny] = 1;
				}
			}
			front++;
		}
	}

	public static int zone() {
		int count = 0;
		visit = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (visit[i][j] == 0) {
					count++;
					BFS(i, j, a[i][j]);
				}
			}
		}

		return count;
	}

	public static int BFS_DT(int x, int y, int v) {
		int front = 0, rear = 0;
		qx[front] = x;
		qy[front] = y;
//		vis[x][y] = 1;
		while (front <= rear) {
			int xt = qx[front], yt = qy[front];
//			System.out.println("dt " + xt + " " + yt +" "+v);
			for (int i = 0; i < 4; i++) {
				int nx = xt + dx[i], ny = yt + dy[i];
				if (checkOut(nx, ny) && visit[nx][ny] == 0 && visit[nx][ny] != 5 && a[nx][ny] == v) {
					rear++;
					qx[rear] = nx;
					qy[rear] = ny;
					visit[nx][ny] = 1;
				}
			}
			front++;
		}
		return rear + 1;
	}

	public static void run() {
		visit = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (a[i][j] == 0 && visit[i][j] == 0) {// tim o 0
					dientich = new int[6];
					int front = 0, rear = 0;
					quex[rear] = i;
					quey[rear] = j;
					rear++;
					visit[i][j] = 1;
//					System.out.println("push " + i + " " + j);
					while (front < rear) {
						int xt = quex[front], yt = quey[front];
						for (int p = 0; p < 4; p++) {
							int nx = xt + dx[p], ny = yt + dy[p];
							if (checkOut(nx, ny) && visit[nx][ny] == 0
									&& a[nx][ny] == 0) {
								quex[rear] = nx;
								quey[rear] = ny;
								rear++;
								visit[nx][ny] = 1;
//								System.out.println("push " + nx + " " + ny);
							}
						}

						front++;
					}
					
					
					front = 0;
					vis = new int[n][n];
					while (front < rear) {
						int xt = quex[front], yt = quey[front];
						for (int p = 0; p < 4; p++) {
							int nx = xt + dx[p], ny = yt + dy[p];
							if (checkOut(nx, ny) && visit[nx][ny] == 0
									&& a[nx][ny] != 0) {
								visit[nx][ny] = 1;
								dientich[a[nx][ny]] += BFS_DT(nx, ny, a[nx][ny]);
							}
						}

						front++;
					}
					
					
					
					for (int p = 0; p < n; p++) {
						for (int q = 0; q < n; q++) {
							if (a[p][q] != 0 && visit[p][q] == 1) {
								visit[p][q] = 0;
							}
						}
					}
					int max = 0, value = 0;
					for (int p = 1; p < 6; p++) {
//						System.out.print(dientich[p] + " ");
						if (dientich[p] >= max) {
							max = dientich[p];
							value = p;
						}
					}
//					System.out.println();
//					System.out.println("max : " + value);
					for (int p = 0; p < rear; p++) {
//						System.out.println(quex[p] + " " + quey[p]);
						a[quex[p]][quey[p]] = value;
						visit[quex[p]][quey[p]] = 5;
					}
//					System.out.println("----------");
				}
			}
		}
	}

	public static void main(String[] args) {
		try {
			System.setIn(new FileInputStream("input.txt"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		Scanner scanner = new Scanner(System.in);
		int test = scanner.nextInt();
		for (int t = 1; t <= test; t++) {
			n = scanner.nextInt();
			a = new int[n][n];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					a[i][j] = scanner.nextInt();
				}
			}
			run();

			System.out.println("Case #" + t + "\n" + zone());

		}
		scanner.close();
	}
}