#include <cstdio>
#include <queue>
#include <algorithm>
//#include <graphics.h>
using namespace std;
int n, c;
char col[26][26];
char vis[26][26];
void colordfs(int x, int y) {
	vis[x][y] = 1;
	if (x > 0 && vis[x - 1][y] != 1) {
		if (col[x][y] == col[x - 1][y]) colordfs(x - 1, y);
		else vis[x - 1][y] = 2;
	}
	if (x < n - 1 && vis[x + 1][y] != 1) {
		if (col[x][y] == col[x + 1][y]) colordfs(x + 1, y);
		else vis[x + 1][y] = 2;
	}
	if (y > 0 && vis[x][y - 1] != 1) {
		if (col[x][y] == col[x][y - 1]) colordfs(x, y - 1);
		else vis[x][y - 1] = 2;
	}
	if (y < n - 1 && vis[x][y + 1] != 1) {
		if (col[x][y] == col[x][y + 1]) colordfs(x, y + 1);
		else vis[x][y + 1] = 2;
	}
}
char vis222[26][26];
queue<pair<int, int> > q;
void colordfs2(int x, int y) {
	vis222[x][y] = 1;
	if (x > 0 && vis222[x - 1][y] != 1) {
		if (col[x][y] == col[x - 1][y]) colordfs2(x - 1, y);
		else vis222[x - 1][y] = 2, q.push(make_pair(x - 1, y));
	}
	if (x < n - 1 && vis222[x + 1][y] != 1) {
		if (col[x][y] == col[x + 1][y]) colordfs2(x + 1, y);
		else vis222[x + 1][y] = 2, q.push(make_pair(x + 1, y));
	}
	if (y > 0 && vis222[x][y - 1] != 1) {
		if (col[x][y] == col[x][y - 1]) colordfs2(x, y - 1);
		else vis222[x][y - 1] = 2, q.push(make_pair(x, y - 1));
	}
	if (y < n - 1 && vis222[x][y + 1] != 1) {
		if (col[x][y] == col[x][y + 1]) colordfs2(x, y + 1);
		else vis222[x][y + 1] = 2, q.push(make_pair(x, y + 1));
	}
}
bool colorit(int tocol) {
	bool flg = 0;
	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (vis[i][j] == 2 && col[i][j] == tocol) colordfs(i, j), flg = 1;
	return flg;
}
int calcwill() {
	bool tmp[8] = {};
	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (vis[i][j] != 1) tmp[(int)col[i][j]] = 1;
	int res = 0; for (int i = 0; i < 8; i++) res += tmp[i];
	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
		vis222[i][j] = vis[i][j]; if (vis222[i][j] == 2) q.push(make_pair(i, j));
	}
	int dep = 0, nowsize = q.size();
	while (nowsize) {
		for (int i = 0; i < nowsize; i++) {
			if (vis222[q.front().first][q.front().second] == 2) colordfs2(q.front().first, q.front().second);
			q.pop();
//			printf("pop at %d\n", q.size());
		}
		nowsize = q.size();
		dep++;
	}
//	printf("dep %d res %d\n", dep, res);
	return max(res, dep);
}
int IDAStar(int d, int maxd, int firstst = -1) {
	int cw = calcwill();
	if (d + cw > maxd) return -1; if (cw == 0) return firstst;
	char vis2[26][26];
	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) vis2[i][j] = vis[i][j];
	for (int i = 0; i < c; i++) {
		if (colorit(i)) {
			int cc = IDAStar(d + 1, maxd, firstst == -1 ? i : firstst);
			for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) vis[i][j] = vis2[i][j];
			if (cc != -1) return cc;
		}
		for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) vis[i][j] = vis2[i][j];
	}
	return -1;
}
void mainpath() {
	vis[0][0] = 2;
	colorit(col[0][0]);
	int res = 0, cc;
	int path[1000];
	for (; ; res++) {
//		printf("trying %d\n", res);
		if ((cc = IDAStar(0, res)) != -1) {
			path[0] = cc;
//			printf("get %d\n", cc);
			break;
		}
	}
	printf("%d\n", res);
//	for (int i = 1; i < res; i++) {
//		colorit(path[i - 1]);
//		path[i] = IDAStar(i, res);
//	}
//	for (int i = 0; i < res; i++) printf("%d ", path[i]);
//	puts("");
}
int main() {
//	scanf("%d %d", &n, &c);
//	for (int i = 0; i < n; i++) {
//		for (int j = 0; j < n; j++) scanf("%d", &col[i][j]);
//	}
//	mainpath();
	c = 6;
	while (~scanf("%d", &n)) {
		if (n == 0) break;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) scanf("%d", &col[i][j]);
		}
		mainpath();
	}
	return 0;
}
/*
8 6
1 4 2 3 1 0 4 2
2 4 2 5 1 0 0 5
0 2 1 0 3 4 2 4
0 5 3 4 3 5 2 4
2 3 5 1 2 2 1 0
2 4 4 3 0 5 3 0
1 2 0 1 2 3 2 3
4 2 2 5 4 5 5 1

12
1 4 2 3 1 0 4 2 1 4 2 3
2 4 2 5 1 0 0 5 2 4 2 5
0 2 1 0 3 4 2 4 0 2 1 0
0 5 3 4 3 5 2 4 0 5 3 4
2 3 5 1 2 2 1 0 2 3 5 1
2 4 4 3 0 5 3 0 2 4 4 3
1 2 0 1 2 3 2 3 1 2 0 1
4 2 2 5 4 5 5 1 4 2 2 5
1 4 2 3 1 0 4 2 1 4 2 3
2 4 2 5 1 0 0 5 2 4 2 5
0 2 1 0 3 4 2 4 0 2 1 0
0 5 3 4 3 5 2 4 0 5 3 4

10 6
1 3 3 5 4 1 1 2 2 0
0 1 0 4 1 3 0 2 3 2
0 0 4 1 2 4 0 4 5 3
4 5 2 1 4 5 4 4 1 2
1 0 3 4 1 4 4 2 2 5
5 4 3 5 0 4 3 2 1 5
1 3 2 0 0 5 5 3 1 4
2 1 0 4 3 0 5 4 0 2
4 0 0 0 1 2 0 4 3 0
5 3 2 1 5 5 1 3 1 4

10 3
1 1 1 1 1 1 1 2 1 0
0 0 0 2 2 0 2 2 0 0
1 1 2 2 2 0 1 1 1 0
2 2 1 1 1 0 1 2 0 1
0 0 0 2 1 0 2 2 1 1
1 1 1 2 2 0 0 0 0 2
0 2 0 2 0 1 1 1 2 1
0 0 0 1 1 2 0 1 2 1
0 0 1 0 1 0 0 1 2 0
1 1 0 1 0 1 2 1 2 2
*/

在题解的基础上添加了最少层数优化