#include <cstdio>
#include <string>
#include <queue>
#include <map>
using namespace std;
 
int N;
 
void fill(string& s, int r, int c, int change, int color) {
  s[r * N + c] = color;
  if (r + 1 < N && s[(r + 1) * N + c] == change) fill(s, r + 1, c, change, color);
  if (c + 1 < N && s[r * N + c + 1] == change) fill(s, r, c + 1, change, color);
  if (r && s[(r - 1) * N + c] == change) fill(s, r - 1, c, change, color);
  if (c && s[r * N + c - 1] == change) fill(s, r, c - 1, change, color);
}
 
bool check(string& s) {
  for (int i = 1; i < N * N; i++)
    if (s[i] != s[0]) return 0;
  return 1;
}
 
int main() {
  while (scanf("%d", &N) && N) {
    int i, tmp, max = 0;
    string source;
    for (i = 0; i < N * N; i++) {
        scanf("%d", &tmp);
        max = tmp > max ? tmp : max;
        source.insert(source.end(), tmp + '0');
    }
    if (check(source)) {
      puts("0");
      continue;
    }
    queue<string> q;
    map<string, int> dis;
    q.push(source);
    dis[source] = 0;
    bool find = 0;
    while (!q.empty() && !find) {
      string now = q.front();
      int d = dis[now];
      q.pop();
      for (int color = '0'; color <= max + '0'; color++) {
        if (color == now[0]) continue;
        string next = now;
        fill(next, 0, 0, now[0], color);
        if (check(next)) {
          printf("%d\n", d + 1);
          find = 1;
          break;
        }
        if (!dis.count(next)) {
          q.push(next);
          dis[next] = d + 1;
        }
      }
    }
  }
  return 0;
}
 

I2luY2x1ZGUgPGNzdGRpbz4KI2luY2x1ZGUgPHN0cmluZz4KI2luY2x1ZGUgPHF1ZXVlPgojaW5jbHVkZSA8bWFwPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IE47Cgp2b2lkIGZpbGwoc3RyaW5nJiBzLCBpbnQgciwgaW50IGMsIGludCBjaGFuZ2UsIGludCBjb2xvcikgewogIHNbciAqIE4gKyBjXSA9IGNvbG9yOwogIGlmIChyICsgMSA8IE4gJiYgc1sociArIDEpICogTiArIGNdID09IGNoYW5nZSkgZmlsbChzLCByICsgMSwgYywgY2hhbmdlLCBjb2xvcik7CiAgaWYgKGMgKyAxIDwgTiAmJiBzW3IgKiBOICsgYyArIDFdID09IGNoYW5nZSkgZmlsbChzLCByLCBjICsgMSwgY2hhbmdlLCBjb2xvcik7CiAgaWYgKHIgJiYgc1sociAtIDEpICogTiArIGNdID09IGNoYW5nZSkgZmlsbChzLCByIC0gMSwgYywgY2hhbmdlLCBjb2xvcik7CiAgaWYgKGMgJiYgc1tyICogTiArIGMgLSAxXSA9PSBjaGFuZ2UpIGZpbGwocywgciwgYyAtIDEsIGNoYW5nZSwgY29sb3IpOwp9Cgpib29sIGNoZWNrKHN0cmluZyYgcykgewogIGZvciAoaW50IGkgPSAxOyBpIDwgTiAqIE47IGkrKykKICAgIGlmIChzW2ldICE9IHNbMF0pIHJldHVybiAwOwogIHJldHVybiAxOwp9CgppbnQgbWFpbigpIHsKICB3aGlsZSAoc2NhbmYoIiVkIiwgJk4pICYmIE4pIHsKICAgIGludCBpLCB0bXAsIG1heCA9IDA7CiAgICBzdHJpbmcgc291cmNlOwogICAgZm9yIChpID0gMDsgaSA8IE4gKiBOOyBpKyspIHsKICAgICAgICBzY2FuZigiJWQiLCAmdG1wKTsKICAgICAgICBtYXggPSB0bXAgPiBtYXggPyB0bXAgOiBtYXg7CiAgICAgICAgc291cmNlLmluc2VydChzb3VyY2UuZW5kKCksIHRtcCArICcwJyk7CiAgICB9CiAgICBpZiAoY2hlY2soc291cmNlKSkgewogICAgICBwdXRzKCIwIik7CiAgICAgIGNvbnRpbnVlOwogICAgfQogICAgcXVldWU8c3RyaW5nPiBxOwogICAgbWFwPHN0cmluZywgaW50PiBkaXM7CiAgICBxLnB1c2goc291cmNlKTsKICAgIGRpc1tzb3VyY2VdID0gMDsKICAgIGJvb2wgZmluZCA9IDA7CiAgICB3aGlsZSAoIXEuZW1wdHkoKSAmJiAhZmluZCkgewogICAgICBzdHJpbmcgbm93ID0gcS5mcm9udCgpOwogICAgICBpbnQgZCA9IGRpc1tub3ddOwogICAgICBxLnBvcCgpOwogICAgICBmb3IgKGludCBjb2xvciA9ICcwJzsgY29sb3IgPD0gbWF4ICsgJzAnOyBjb2xvcisrKSB7CiAgICAgICAgaWYgKGNvbG9yID09IG5vd1swXSkgY29udGludWU7CiAgICAgICAgc3RyaW5nIG5leHQgPSBub3c7CiAgICAgICAgZmlsbChuZXh0LCAwLCAwLCBub3dbMF0sIGNvbG9yKTsKICAgICAgICBpZiAoY2hlY2sobmV4dCkpIHsKICAgICAgICAgIHByaW50ZigiJWRcbiIsIGQgKyAxKTsKICAgICAgICAgIGZpbmQgPSAxOwogICAgICAgICAgYnJlYWs7CiAgICAgICAgfQogICAgICAgIGlmICghZGlzLmNvdW50KG5leHQpKSB7CiAgICAgICAgICBxLnB1c2gobmV4dCk7CiAgICAgICAgICBkaXNbbmV4dF0gPSBkICsgMTsKICAgICAgICB9CiAgICAgIH0KICAgIH0KICB9CiAgcmV0dXJuIDA7Cn0K

MiAKMCAwICAKMCAwIAozIAowIDEgMiAKMSAxIDIgCjIgMiAxIAo0CjEgMCAyIDAKMSAyIDAgMwoyIDAgMyA0CjUgMSAxIDQKNwowIDEgMiAzIDQgNSA0CjQgNSA0IDMgMiAxIDQKMCAxIDIgMyA0IDUgNAo0IDUgNCAzIDIgMSA0CjAgMSAyIDMgNCA1IDQKNCA1IDQgMyAyIDEgMAowIDEgMiAzIDQgNSA0CjcKMCAxIDIgMyA0IDUgNAo0IDUgNCAzIDIgMSAwCjAgMSAyIDMgNCA1IDQKNCA1IDQgMyAyIDEgMAowIDEgMiAzIDQgNSA0CjQgNSA0IDMgMiAxIDAKMCAxIDIgMyA0IDUgNAo4CjAgMSAyIDMgNCA1IDQgMwozIDQgNSA0IDMgMiAxIDAKMCAxIDIgMyA0IDUgNCAzCjMgNCA1IDQgMyAyIDEgMAowIDEgMiAzIDQgNSA0IDMKMyA0IDUgNCAzIDIgMSAwCjAgMSAyIDMgNCA1IDQgMwozIDQgNSA0IDMgMiAxIDAKMA==

2 
0 0  
0 0 
3 
0 1 2 
1 1 2 
2 2 1 
4
1 0 2 0
1 2 0 3
2 0 3 4
5 1 1 4
7
0 1 2 3 4 5 4
4 5 4 3 2 1 4
0 1 2 3 4 5 4
4 5 4 3 2 1 4
0 1 2 3 4 5 4
4 5 4 3 2 1 0
0 1 2 3 4 5 4
7
0 1 2 3 4 5 4
4 5 4 3 2 1 0
0 1 2 3 4 5 4
4 5 4 3 2 1 0
0 1 2 3 4 5 4
4 5 4 3 2 1 0
0 1 2 3 4 5 4
8
0 1 2 3 4 5 4 3
3 4 5 4 3 2 1 0
0 1 2 3 4 5 4 3
3 4 5 4 3 2 1 0
0 1 2 3 4 5 4 3
3 4 5 4 3 2 1 0
0 1 2 3 4 5 4 3
3 4 5 4 3 2 1 0
0