重排九宫是一个古老的单人智力游戏。据说重排九宫起源于我国古时由三国演义故事“关羽义释曹操”而设计的智力玩具“华容道”，后来流传到欧洲，将人物变成数字。原始的重排九宫问题是这样的：将数字1～8 按照任意次序排在3´3 的方格阵列中，留下一个空格。与空格相邻的数字，允许从上，下，左，右方向移动到空格中。游戏的最终目标是通过合法移动，将数字1～8 按行排好序。在一般情况下，n2-1 谜问题是将数字1～n²-1 按照任意次序排在n*n的方格阵列中，留下一个空格。允许与空格相邻的数字从上，下，左，右4 个方向移动到空格中。游戏的最终目标是通过合法移动，将初始状态变换到目标状态。n²-1谜问题的目标状态是将数字1～n²-1 按从小到大的次序排列，最后一个位置为空格。

图5-15 重排九宫

对于给定的n*n方格阵列中数字1～n²-1初始排列，计算将初始排列通过合法移动变换为目标状态最少移动次数。

输入数据。文件的第1行有1 个正整数n。以下的n行是n*n方格阵列的中数字1～n²-1的初始排列，每行有n个数字表示该行方格中的数字， 0 表示空格。

将计算出的最少移动次数和相应的移动序列输出，第1 行是最少移动次数。从第2 行开始，依次输出移动序列。