회전하는 고리

정사각형 격자는 안쪽으로 겹겹이 들어간 하나 이상의 고리(ring)로 볼 수 있습니다. 예를 들어 그림 (a)처럼 $5 \times 5$ 격자는 바깥쪽부터 안쪽으로 $1, 2, 3$번이 매겨진 세 개의 고리로 이루어져 있습니다. 크기가 $N$인 정사각형 격자가 정렬된(sorted) 상태라는 것은, 그림 (b)의 $N = 4$ 예시처럼 $1$부터 $N^2$까지의 값이 행 우선(row-major) 순서로 들어 있는 것을 뜻합니다.

주어진 정사각형 격자를 오직 고리 회전만으로 정렬할 수 있는지 판정하려 합니다. 각 고리는 다른 고리와 독립적으로, 시계 방향 또는 반시계 방향으로 원하는 만큼 회전할 수 있습니다. 예를 들어 그림 (c)의 격자는 바깥 고리를 반시계 방향으로 두 칸, 두 번째 고리를 시계 방향으로 한 칸 회전하면 정렬됩니다.

각 격자에 대해 이러한 방식으로 정렬이 가능한지 판정하세요.

입력은 하나 이상의 테스트 케이스로 이루어집니다. 각 테스트 케이스의 첫 줄에는 격자의 크기를 나타내는 정수 $N$이 주어집니다. 이어지는 $N$개의 줄에는 각 줄마다 $N$개의 정수가 행 우선 순서로 격자 값으로 주어집니다.

$0 < N \le 1000$ 이며, 모든 격자 값은 $10^6$ 이하의 자연수입니다.

입력의 끝은 $N = 0$인 줄로 표시되며, 이 줄은 처리하지 않습니다.

각 테스트 케이스마다 다음 형식으로 한 줄을 출력합니다.

k. result

여기서 $k$는 테스트 케이스 번호($1$부터 시작)이고, 그 뒤에 마침표와 공백 한 칸이 오며, result는 고리 회전만으로 정렬할 수 있으면 YES, 그렇지 않으면 NO입니다.