코메디아 델라르테

코메디아 델라르테(Commedia dell'arte)는 16세기 초 이탈리아에서 처음 등장한 연극 장르로, 로마 연극에서 영감을 받았다. 이 연극에는 정해진 대본이 없어서 배우(연기자라고도 한다)들은 끊임없이 즉흥 연기를 해야 했다. 작가는 "무대에 올라 뭔가 우스운 것을 하라" 또는 "모두 무대에 올라 모든 일이 즐겁게 마무리된다" 같은 대략적인 지시만 주었다.

한 극단이 완전히 새로운 연극을 무대에 올리려 한다. 주인공은 극에서 중요한 역할을 하며 즉흥 연기의 여지를 크게 넓혀 주는 퍼즐 하나를 가지고 있다. 이 퍼즐은 세계적으로 유명한 15 퍼즐인데, 극을 더 흥미롭게 만들기 위해 극단은 표준 퍼즐을 3차원 퍼즐로 바꾸기로 했다.

3차원 퍼즐은 $M^3$개의 칸으로 이루어진 정육면체다. 한 칸을 제외한 모든 칸에는 정육면체 타일이 하나씩 들어 있고, 정확히 한 자리가 비어 있다. 타일에는 $1$부터 $M^3 - 1$까지 번호가 매겨져 있다. 목표는 타일을 무작위로 뒤섞은 뒤 원래 순서로 되돌리는 것이다. 허용되는 유일한 이동은, 빈 칸과 인접한 타일을 세 주축 방향 중 하나를 따라 빈 칸으로 밀어 넣는 것이다.

원래(목표) 배치에서 좌표 $(x, y, z)$ ($x, y, z \in {0, \dots, M-1}$)의 칸에는 번호 $z \cdot M^2 + y \cdot M + x + 1$인 타일이 들어 있고, 칸 $(M-1, M-1, M-1)$이 비어 있다.

퍼즐을 풀 수 있는지 판정하는 프로그램을 작성하라.

입력은 $N$개의 테스트 케이스로 이루어진다. 첫 줄에는 양의 정수 $N$이 하나 주어지고, 이어서 각 케이스가 주어진다.

각 케이스의 첫 줄에는 정육면체의 한 변의 길이를 나타내는 정수 $M$ ($1 \le M \le 100$)이 주어진다. 이어지는 $M$개의 줄에는 각각 한 층(layer)을 나타내는 $M^2$개의 수가 주어진다. 첫 줄은 정육면체의 맨 위 층, 마지막 줄은 맨 아래 층이다. 한 층 안에서 수는 왼쪽 위 구석에서 오른쪽 아래 구석까지 행 단위로 나열된다. 즉, 좌표 $(x, y, z)$의 칸은 $(z + 1)$번째 줄의 $(x + M \cdot y + 1)$번째 수로 표현된다. 수는 공백으로 구분되며, $0$은 빈 자리를 뜻한다.

각 케이스마다 정확히 한 줄을 출력한다. 타일을 밀어서 원래 배치에 도달할 수 있으면 Puzzle can be solved.를, 그렇지 않으면 Puzzle is unsolvable.를 출력한다.