SP45 COMMEDIA - Commedia dell Arte

所谓“即兴喜剧”是一种戏剧类型，最早的演出可追溯至十六世纪初的意大利。其灵感来源于古罗马大剧场。这种表演没有固定的剧本，演员需要做出大量的即兴发挥。创作者只会给出一个简单的方向，譬如“走上舞台并做一些搞笑的事”，或者“每个人都上台，结果皆大欢喜”。你可以发现，表演即兴喜剧可能会非常有趣。因此，ACM想安排一场前所未见的演出。英雄主角遇到了一个拼图。这个拼图在剧中扮演了非常重要的角色，提供了许多即兴创作的机会。它就是世界知名的“劳埃德15拼图”。ACM想让表演变得更加有趣，所以他们想用一个三维的问题替代“标准”的拼图。 这个拼图由一个立方体组成，包括了$M^{3}$个插槽。除了一个插槽以外，每个插槽都包含了一个三维拼图块（或者说，有一个位置是空的）。拼图块从$1$到$m^{3}-1$依次编号。拼图的目标在于，在拼图块随机洗牌后，恢复它们的原始顺序。唯一允许的动作是：沿着三个主方向之一，将临近的拼图块移动至空位置。原始布局规定如下：任意被赋予了在$\{0,\dots,M-1\}^3$范围内的坐标$(x,y,z)$的拼图块，其编号为$z\cdot M^{2}+y\cdot M+x+1$，并且$(M-1,M-1,M-1)$为空位置。 你需要写一个程序，确定拼图是否可解。

输入包含$N$组数据。输入第一行只有一个正整数$N$。然后输入每组数据。每组数据的第一行包括了一个正整数$M$，$1\leq M\leq 100$，$M$是拼图立方体的的大小。接下来的$M$行，每行包括了$M^{2}$个数，从顶层到底层给出了每一层插槽集合的数据。每一层的数据按行主序从左上角到右下角排列。换句话说，插槽$(x,y,z)$由第$z+1$行的第$(x+M\cdot y+1)$个数据描述。数据之间由空格隔开。$0$代表空位置。

对每一组数据，输出一行。如果能通过滑动拼图块恢复原始布局，输出Puzzle can be solved. 否则输出Puzzle is unsolvable.

警告：输入输出量很大，使用某些语言时应注意