#include<cstdio> 
#include<cstdlib> 
#include<cstring> 
#include<set> 
#include<algorithm> 
#include<map> 
#include<vector> 
#include<queue> 
#include<iostream> 
#include<string> 
#include<cmath> 
#define N 9 
#define FOR(i,a,b) for(i=(a);i<=(b);i++) 
#define ROF(i,a,b) for(i=(a);i>=(b);i--) 
#define mmt(a,b) memset(a,b,sizeof(a)) 
typedef long long LL; 
using namespace std; 
int dx[4]={-1,1,0,0}; 
int dy[4]={0,0,-1,1}; 
int a[9][9],v[9][9],n,dep;
bool f,bb[9]; 
void floodfill(int x,int y,int c) 
{ 
   v[x][y]=1;int i;
   FOR(i,0,3) 
   { 
     int tx=x+dx[i],ty=y+dy[i]; 
     if (tx&&ty&&tx<=n&&ty<=n&&v[tx][ty]!=1) 
     {
       v[tx][ty]=2;
       if (a[tx][ty]==c) floodfill(tx,ty,c);
     }
   } 
} 
bool extend(int col)
{
  int i,j,r=0;
  FOR(i,1,n) FOR(j,1,n) 
   if (a[i][j]==col&&v[i][j]==2) 
   {
     floodfill(i,j,col);
     r=1;
   }
  return r;
}
int ccol()
{
  int i,j,res=0;
  mmt(bb,0);
  FOR(i,1,n) FOR(j,1,n) 
   if (!bb[a[i][j]]&&v[i][j]!=1) {bb[a[i][j]]=1;res++;}
  return res;
}
void DFS(int step) 
{ 
   int g=ccol(); 
   if (f) return; 
   if (step+g>dep) return; 
   if (!g) {f=1;return;} 
   int tmp[9][9];
   int i;
   memcpy(tmp,v,sizeof(v));
   FOR(i,0,5)
   {
     memcpy(v,tmp,sizeof(v));
     int p=extend(i);
     if (!p) continue;
     DFS(step+1);
   }
} 
int IDAStar() 
{ 
   mmt(v,0);
   int i,j;v[1][1]=2;
   floodfill(1,1,a[1][1]);
   int tmp[9][9];
   memcpy(tmp,v,sizeof(v));
   for(dep=0;;dep++) 
   { 
     f=0;memcpy(v,tmp,sizeof(v));
     DFS(0); 
     if (f) return dep; 
   } 
} 
void Main() 
{ 
   if (n==0) return;
   int i,j;
   FOR(i,1,n) FOR(j,1,n) scanf("%d",&a[i][j]); 
   int ans=IDAStar(); 
   printf("%d\n",ans); 
} 
int main() 
{ 
   while (scanf("%d",&n)!=EOF) Main();
}