题目描述

Flood-it 是 Google+ 平台上一款有趣的益智游戏。游戏界面如下：

游戏开始时，系统会随机生成一个 $N \times N$ 的方形棋盘，棋盘的每个格子被涂成六种颜色之一。玩家从棋盘的左上角开始。每一步，玩家选择一种颜色，并将与左上角相连的所有格子更改为该颜色。这里的“两个格子相连”指的是这两个格子之间存在一条路径，该路径上的每一对相邻格子颜色相同且共享一条边。通过这种方式，玩家可以从起始格子（左上角）开始“淹没”棋盘区域，直到所有格子都变为同一种颜色。下图展示了一个 $4 \times 4$ 游戏的最初几步（颜色用 $0$ 到 $5$ 标记）：

给定初始棋盘的颜色分布，请找出赢得游戏（将所有格子变为同一种颜色）所需的最少步数。

输入格式：

输入包含不超过 $20$ 个测试用例。每个测试用例的第一行包含一个整数 $N$（$2 \leq N \leq 8$），表示棋盘的大小。接下来的 $N$ 行展示一个 $N \times N$ 的矩阵 $(a_{i,j})_{n \times n}$，表示棋盘。$a_{i,j}$ 的取值范围是 $0$ 到 $5$，表示对应格子的颜色。输入以 $N = 0$ 结束。

输出格式：

对于每个测试用例，输出一个整数，表示赢得游戏所需的最少步数。

样例输入 1：

2
0 0 
0 0
3
0 1 2
1 1 2
2 2 1
0

样例输出 1：

0
3