Commedia dell'arte

Commedia dell'arte is a theater genre that first appeared in Italy at the start of the 16th century, inspired by Roman theater. The plays had no fixed script, so the actors (also called performers) had to improvise constantly — the author gave only loose directions such as "enter the stage and do something funny" or "everyone comes on stage and everything ends happily."

A theater company wants to stage a brand-new play. Its hero owns a puzzle that plays a central role and opens up many chances to improvise. The puzzle is the world-famous Fifteen Puzzle, but to make the play more interesting the company replaces the standard puzzle with a three-dimensional version.

The 3D puzzle is a cube of $M^3$ slots. Every slot but one holds a cubic tile; exactly one position is free. The tiles are numbered from $1$ to $M^3 - 1$. The goal is to restore the original ordering after the tiles have been randomly reshuffled. The only allowed move is to slide a tile that is adjacent to the free position into that free position, along one of the three principal axes.

In the original (goal) configuration, the slot at coordinates $(x, y, z)$ with $x, y, z \in {0, \dots, M-1}$ holds tile number $z \cdot M^2 + y \cdot M + x + 1$, and the slot $(M-1, M-1, M-1)$ is free.

Write a program that decides whether the puzzle can be solved.

The input consists of $N$ cases. The first line contains a single positive integer $N$. The cases follow.

The first line of each case contains one integer $M$ ($1 \le M \le 100$), the side length of the cube. Then follow $M$ lines, each containing exactly $M^2$ numbers that describe one layer: the first line is the top layer of the cube and the last line is the bottom layer. Within a layer the numbers are listed row by row, from the top-left corner to the bottom-right corner. Equivalently, the slot at coordinates $(x, y, z)$ is the $(x + M \cdot y + 1)$-th number on the $(z + 1)$-th line. Numbers are separated by spaces, and $0$ marks the free position.

For each case print exactly one line. If the original configuration can be reached by sliding the tiles, print Puzzle can be solved. Otherwise print Puzzle is unsolvable.