#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;
}