Rotating Rings#1627
Any square grid can be considered as one or more rings, nested within each other. For example, as shown in figure (a), a 5 \times 5 grid consists of three rings, numbered , , and (from outside to inside). A square grid of size is considered sorted if it contains the values from to N^2 in row-major order, as shown in figure (b) for N = 4. We want to determine whether a given square grid can be sorted by only rotating its rings. For example, the grid in figure (c) can be sorted by rotating the first ring two places counterclockwise, and the second ring one place clockwise.
Your program will be tested on one or more test cases. The first input line of a test case is an integer — the size of the grid. input lines follow, each containing integer values specifying the values in the grid in row-major order. Note that 0 < N \leq 1000, and the grid values are natural numbers not greater than .
The end of input is indicated by a dummy test case with N = 0.
For each test case, output the result on a single line in the following format:
k. result
where is the test case number (starting at ), and result is YES or NO (without the double quotes).
Example 1