Rotating Rings

Any square grid can be viewed as one or more concentric rings, one inside another. For example, as shown in figure (a), a $5 \times 5$ grid is made of three rings, numbered $1$, $2$, and $3$ from the outside inward. A square grid of size $N$ is said to be sorted if it contains the values from $1$ to $N^2$ in row-major order, as shown in figure (b) for $N = 4$.

We want to decide whether a given square grid can be sorted using only ring rotations. Each ring may be rotated by any number of positions, clockwise or counter-clockwise, independently of the other rings. For example, the grid in figure (c) can be sorted by rotating the outer ring two positions counter-clockwise and the second ring one position clockwise.

For each grid, determine whether it can be sorted in this way.

The input consists of one or more test cases. Each test case begins with a line containing an integer $N$, the size of the grid. The next $N$ lines each contain $N$ integers giving the grid values in row-major order.

You may assume $0 < N \le 1000$, and every grid value is a natural number at most $10^6$.

The input ends with a line containing $N = 0$, which must not be processed.

For each test case, print a single line in the format:

k. result

where $k$ is the test case number (starting from $1$), followed by a period and a single space, and result is YES if the grid can be sorted using only ring rotations, or NO otherwise.