题目描述

所谓的即兴喜剧（commedia dell'arte）是$16$世纪初起源于意大利的一种戏剧形式，其灵感来自古罗马戏剧。这种表演没有固定剧本，演员（也称为表演者）需要大量即兴发挥。作者只会给出简单的指示，如"上台做些有趣的事"或"所有人上台后问题都愉快解决"。可以想象，表演即兴喜剧会非常有趣。因此，ACM想要上演一部全新的即兴喜剧。剧中的主角有一个谜题，这个谜题在剧中扮演重要角色，并为即兴表演提供了许多机会。这个谜题就是世界著名的"十五滑块游戏"（Lloyd's Fifteen Puzzle）。ACM为了让表演更有趣，决定用三维版本替换"标准"的二维谜题。

这个三维谜题由一个包含$M^3$个格子的立方体组成。除一个格子外，其他每个格子都包含一个立方体滑块（有一个位置是空的）。滑块编号从$1$到$M^3-1$。谜题的目标是通过移动滑块，将打乱顺序的滑块恢复到原始排列。唯一允许的移动操作是：沿着三个主要方向之一，将相邻的滑块滑入空格。原始配置是指坐标为$(x,y,z)$（其中$x,y,z∈\{0,...,M-1\}$）的格子包含编号为$z·M^2+y·M+x+1$的滑块，且坐标$(M-1,M-1,M-1)$的格子为空。

你需要编写一个程序来判断给定的三维滑块拼图是否可解。

输入格式

输入包含$N$个测试用例。第一行仅包含正整数$N$。随后是各测试用例：

• 每个用例的第一行包含一个整数$M$（$1 \leq M \leq 100$），表示立方体的尺寸
• 接着是$M$行输入，每行包含$M^2$个数字，描述立方体的一个层。第一行表示最顶层，最后一行表示最底层
• 每层中的数字从左上方到右下方按行排列。换句话说，坐标为$(x,y,z)$的格子对应第$(z+1)$行输入的第$(x+M·y+1)$个数字
• 数字$0$表示空格

输出格式

对于每个测试用例，输出一行：

• 如果拼图可解，输出"Puzzle can be solved."
• 否则输出"Puzzle is unsolvable."

输入样例

2
2
1 2 3 4
5 7 6 0
2
2 1 3 5
4 6 0 7

输出样例

Puzzle is unsolvable.
Puzzle can be solved.

题目来源

$1998$年中欧地区竞赛