1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int N = 8;
 6 typedef pair<int,int> pnt;
 7 int vis[N][N], num[N][N], n, tp;
 8 pnt Q[N*N];
 9 inline bool fit(int x,int y){
10     return x >= 0 && x < n && y >= 0 && y < n && !vis[x][y];
11 }
12 inline void bfs(int sx,int sy) {
13     int head = 0, tail = 1;
14     vis[sx][sy] = 1;
15     Q[0] = make_pair(sx, sy);
16     int c = num[sx][sy];
17     //cout<< "bfs: "<<endl;
18     //cout<< c << endl;
19     while(head < tail) {
20         pnt u = Q[head ++];
21         for(int i = 0; i < 4; i++){
22             int x = u.first + (i == 0) - (i == 1);
23             int y = u.second + (i == 2) - (i == 3);
24             if(fit(x,y) && num[x][y] == c){
25         //        cout<<"v: "<<x<<" "<<y<<" "<< num[x][y]<<endl;
26                 vis[x][y] = 1;
27                 Q[tail ++] = make_pair(x, y);
28             }}}
29 }
30 typedef unsigned long long ll;
31 inline ll hash(){
32     ll ans = 0;
33     for(int i = 0; i< n; i++)
34         for(int j = 0; j < n; j ++)
35             ans <<= 1, ans ^= vis[i][j];
36     return ans;
37 }
38 inline void rehash(ll t) {
39     for(int i = n-1; i>= 0; i--)
40         for(int j = n-1; j>=0 ;j--, t>>=1)
41             vis[i][j] = t&1;
42 }
43 inline int cal(){
44     int h[6] = {0};
45     for(int i = 0; i < n; i++)
46         for(int j = 0; j< n; j++) if(!vis[i][j])
47             h[num[i][j]] = 1;
48     int ans = 0;
49     for(int i = 0; i < 6; i++)
50         ans += h[i];
51     return ans;
52 }
53 int dfs(int lvl) {
54     //cout<<"lvl: "<<lvl<<endl;
55     if(lvl == tp) return cal() == 0;
56     if(cal()+ lvl > tp) return 0;
57     ll tmp = hash();
58     for(int c = 0; c < 6; c ++){
59         int flag = 0;
60         for(int i = 0; i < n; i++)
61             for(int j = 0; j< n; j++) if(vis[i][j]) {
62                 for(int p = 0; p < 4; p ++ ){
63                     int x = i + (p == 0) - (p == 1);
64                     int y = j + (p == 2) - (p == 3);
65                     if(fit(x,y) && num[x][y] == c){
66                         bfs(x,y);
67                         flag = 1;
68                     }
69             }}
70         if(!flag) continue;
71         if(dfs(lvl + 1)) return 1;
72         rehash(tmp);
73     }
74     return 0;
75 }
76 int main(){
77     while(scanf("%d",&n), n) {
78         for(int i = 0; i < n ; i ++)
79             for(int j = 0; j < n; j++)
80                 scanf("%d",&num[i][j]);
81         memset(vis, 0, sizeof(vis));
82         bfs(0,0);
83         ll tmp = hash();
84         for(tp=cal();;tp++) {
85 //            cout<<tp<<endl;
86             if(dfs(0)) break;
87             rehash(tmp);
88         }
89         printf("%d\n",tp);
90     }
91 }
92