题目描述

地毯上的格子有 $N$ 行 $N$ 列，每个格子用一个 $0∼5$ 之间的数字代表它的颜色。

水叮当可以随意选择一个 $0∼5$ 之间的颜色，然后轻轻地跳动一步，最左上角的格子所在的联通块里的所有格子就会变成她选择的那种颜色。这里连通定义为：两个格子有公共边，并且颜色相同。

由于水叮当是施展轻功来跳舞的，为了不消耗过多的真气，她想知道最少要多少步才能把所有格子的颜色变成一样的。

输入格式

每个测试点包含多组数据。

每组数据的第一行是一个整数 $N$，表示地摊上的格子有 $N$ 行 $N$ 列。

接下来 $N$ 行，每行 $N$ 个数。每个数都在 $0∼5$ 之间，描述了该格子的颜色。

$N=0$ 代表输入的结束。

输出格式

对于每组数据，输出一个整数，表示最少步数。用换行符隔开。

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

0
3

数据范围/提示

对于 $30\%$ 的数据，$N<=5$；

对于 $50\%$ 的数据，$N<=6$；

对于 $70\%$ 的数据，$N<=7$；

对于 $100\%$ 的数据，$N<=8$，每个测试点不多于 $20$ 组数据。