Sudoku Block Rotation Restoration

A valid n-order sudoku consists of an n² × n² grid divided into n × n blocks (sometimes called "boxes"). In a valid sudoku, each row, each column, and each block contains every integer from 0 to n² - 1 exactly once.

Originally, you are given a completely correct sudoku. However, during the design of a web game, some of its blocks were rotated. Each block may have been rotated by 90° (to the left or right) or 180°; thus its current orientation is one of the four possibilities (0°, 90°, 180°, 270° relative to its original form). Unfortunately, you have only one operation available for restoration: you may rotate any block by 90° to the left. Each such left rotation counts as one step. (Multiple rotations on a block are allowed; note that applying 4 consecutive left rotations brings a block back to its current state.)

Your task is to determine the minimum total number of left rotations needed to restore the sudoku into a valid configuration. If it is impossible to obtain a valid sudoku by applying any sequence of left rotations to the blocks, output -1.

Supplementary Details

• The sudoku is of order n: There are n × n blocks and each block is an n × n matrix.
• Input: The first line contains an integer n (the block order). It is followed by n² lines, each line contains n² integers separated by spaces, representing the sudoku grid after some blocks have been rotated.
• Output: A single integer: the minimal number of left rotations (each rotation is 90° left) required to restore a valid sudoku, or -1 if recovery is impossible.

Note: Rotating a block does not change the set of numbers within that block (only their positions), but it will affect the overall arrangement of numbers in the rows and columns.

inputFormat

The input begins with an integer n (1 ≤ n ≤ 3), which denotes the block order. The following n² lines each contain n² integers separated by spaces. These n² × n² numbers represent the sudoku grid after some of its blocks have been rotated. Each integer is in the range [0, n² - 1].

outputFormat

Output a single integer representing the minimum number of left rotations required to restore the board to a valid sudoku configuration. If it is impossible to achieve a valid sudoku using the allowed operations, output -1.

sample

1
5

0