#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
typedef unsigned long long ULL;

int n,m;
int in[8][8];
int id[8][8];
int color[64];
int mm[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int con[64][64];
ULL eg[64][6];
const int H=3333331;
vector<ULL> hash[H];

class State{ 
    public:
	ULL s;
	ULL mask[6];
	int dis;
	State(){
	    s=1;
	    for( int i=0; i<6; i++ ){
		mask[i]=eg[0][i];
	    }
	    dis=0;
	}
	State(ULL y,const State& x){
	    s=y;
	    dis=x.dis+1;
	    y^=x.s;
	    for( int k=0; k<6; k++ ){
		mask[k]=x.mask[k];
	    }
	    for( int j=0; j<n; j++ ){
		if(y&(1ULL<<j)){
		    for( int k=0; k<6; k++ ){
			mask[k]|=eg[j][k];
		    }
		}
	    }
	}
};

inline int find(ULL x){
    int h=x%H;
    for( int i=0; i<hash[h].size(); i++ ){
	if(hash[h][i]==x) return 0;
    }
    hash[h].push_back(x);
    return 1;
}

void flood_fill(int x,int y,int z,int d){
    if(x>=0 && y>=0 && x<m && y<m && in[x][y]==z && id[x][y]==-1){
	id[x][y]=d;
	for( int i=0; i<4; i++ ){
	    flood_fill(x+mm[i][0],y+mm[i][1],z,d);
	}
    }
}

void create_graph(){
    n=0;
    memset(id,-1,sizeof(id));
    memset(con,0,sizeof(con));
    for( int i=0; i<m; i++ ){
	for( int j=0; j<m; j++ ){
	    if(id[i][j]==-1){
		flood_fill(i,j,in[i][j],n);
		color[n]=in[i][j];
		n++;
	    }
	}
    }
    for( int i=0; i<m; i++ ){
	for( int j=0; j<m; j++ ){
	    for( int k=0; k<4; k++ ){
		int dx=i+mm[k][0],dy=j+mm[k][1];
		if(dx>=0 && dy>=0 && dx<m && dy<m){
		    con[id[i][j]][id[dx][dy]]=1;
		}
	    }
	}
    }
    for( int i=0; i<n; i++ ){
	for( int j=0; j<6; j++ ){
	    eg[i][j]=0;
	    for( int k=0; k<n; k++ ){
		if(con[i][k] && color[k]==j){
		    eg[i][j]|=(1ULL<<k);
		}
	    }
	}
    }
}

int main(){
    while(scanf("%d",&m) && m){
	for( int i=0; i<m; i++ ){
	    for( int j=0; j<m; j++ ){
		scanf("%d",&in[i][j]);
	    }
	}
	for( int i=0; i<H; i++ ){
	    hash[i].clear();
	}
	create_graph();
	queue<State> que;
	que.push(State());
	find(1);
	ULL target=n==64?0xffffffffffffffffULL:(1ULL<<n)-1;
	while(!que.empty()){
	    State x=que.front();
	    que.pop();
	    if(x.s==target){
		printf("%d\n",x.dis);
		break;
	    }
	    for( int i=0; i<6; i++ ){
		ULL y=x.s|x.mask[i];
		if(y!=x.s && find(y)){
		    que.push(State(y,x));
		}
	    }
	}
    }
    return 0;
}