题目描述

Flood-it是谷歌 +平台上的非常好玩的一款游戏，游戏界面如下所示：

在游戏开始时，系统将随机生成$\red{N \times N}$的方形区域，并且区域内的每个网格都被涂成了六种颜色中的一种。

玩家从左上角开始游戏。

在每个步骤中，玩家选择一种颜色并将与左上角连通的所有格子（包括左上角）都变成该种颜色。

这里连通定义为：两个格子有公共边，并且颜色相同。

通过这种方式，玩家可以从左上角开始将所有格子都变为同一种颜色。

下图显示了$\red{4 \times 4}$游戏的最早步骤（颜色标记为 $\red 0$ 到 $\red 5$）：

请你求出，给定最初区域以后，最少要多少步才能把所有格子的颜色变成一样的。

输入格式

输入包含不超过$\red{20}$个测试用例。 每个测试用例，第一行包含一个整数$\red N$，表示方形区域大小。 接下里 $\red N$ 行，每行包含$\red N$个整数$\red{（0-5）}$，第 $\red i$ 行第 $\red j$ 个整数表示第 $\red i$ 行第 $\red j$ 列的格子的颜色。 当输入样例 $\red{N=0}$ 时，表示输入终止，该用例无需处理。

输出格式

每个测试用例输出一个占据一行的整数，表示所需最少步数。

样例

输入样例

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

输出样例

0
3

提示

$\red{2≤N≤8}$