#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include <limits.h> using namespace std; const int dx[4] = {0,0,-1,1}; const int dy[4] = {-1,1,0,0};

int i,j,n,step; int v[10][10],a[10][10];

inline bool valid(int x,int y) { return x > 0 && x <= n && y > 0 && y <= n; } inline void dfs(int x,int y,int c) { int i,tx,ty; v[x][y] = 1; for (i = 0; i < 4; i++) { tx = x + dx[i]; ty = y + dy[i]; if (valid(tx,ty) && v[tx][ty] != 1) { if (a[tx][ty] == c) dfs(tx,ty,c); else v[tx][ty] = 2; } } } inline int f() { int i,j,s = 0; bool h[10]; memset(h,0,sizeof(h)); for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) { if (!h[a[i][j]] && v[i][j] != 1) { h[a[i][j]] = true; s++; } } } return s; } inline bool fill(int c) { int i,j,s = 0; for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) { if (a[i][j] == c && v[i][j] == 2) { s++; dfs(i,j,c); } } } return s != 0; } inline bool IDDFS(int dep) { int i,t; int tmp[10][10]; t = f(); if (dep + t > step) return false; if (!t) return true; for (i = 0; i <= 5; i++) { memcpy(tmp,v,sizeof(v)); if (fill(i) && IDDFS(dep+1)) return true; memcpy(v,tmp,sizeof(v)); } return false; } int main() {

while (scanf("%d",&n) != EOF && n)
    {
            memset(v,0,sizeof(v));
            for (i = 1; i <= n; i++)
            {
                    for (j = 1; j <= n; j++)
                    {
                            scanf("%d",&a[i][j]);    
                    }    
            }        
            dfs(1,1,a[1][1]);
            for (i = 0; i <= n * n; i++)
            {
                    step = i;
                    if (IDDFS(0))
                            break;
            }
            printf("%d\n",step);
    }
    
    return 0;

}

#include <stdio.h>
#include <string.h>
#define MAXN 8
int size;
int board[MAXN][MAXN];
int dir[4][2] = { {0, 1}, {1, 0}, {0, -1}, { -1, 0} };
int flags[MAXN][MAXN];
int max_depth;
void update_flags(int i, int j, int color)
{
    if (board[i][j] != color)
    {
        flags[i][j] = 2;
        return;
    }

    flags[i][j] = 1;

    for (int k = 0; k < 4; k++)
    {
        int x = i + dir[k][0];
        int y = j + dir[k][1];

        if (x < 0 || y < 0 || x >= size || y >= size || flags[x][y])
            continue;

        update_flags(x, y, color);
    }
}

int color_count()
{
    int ret = 0;
    int s = 0;

    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            if (flags[i][j] != 1)
                s |= (1 << board[i][j]);
        }
    }

    while (s) {
        ret += s & 1;
        s >>= 1;
    }

    return ret;
}

int dfs(int depth)
{
    if (color_count() > max_depth - depth)
        return 0;

    if (depth == max_depth)
        return 1;

    int temp[MAXN][MAXN];
    int color_exist;

    memcpy(temp, flags, sizeof(flags));


    for (int color = 0; color < 6; color++)
    {
        color_exist = 0;

        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (flags[i][j] == 2 && board[i][j] == color)
                {
                    color_exist = 1;
                    update_flags(i, j, color);
                }
            }
        }

        if (!color_exist)
            continue;
        if (dfs(depth + 1))
            return 1;
        memcpy(flags, temp, sizeof(flags));
    }
    return 0;
}

void solved() {
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++)
            scanf ("%d", &board[i][j]);
    }

    for (max_depth = 0; ; max_depth++)
    {
        memset(flags, 0, sizeof(flags));
        update_flags(0, 0, board[0][0]);

        if (dfs(0))
            break;
    }

    printf ("%d\n", max_depth);
}

int main() {
    //freopen("test.txt", "r", stdin);

    while (scanf("%d", &size), size) {
        solved();
    }

    return 0;
}