Self-decrypted cipher
Petya has decided to encrypt his diary to ensure that no one can read it without his permission. He uses a special cipher for this purpose.
He creates a stencil of N×N cells (N is even), cutting out N^2/4 cells in such a way that when the stencil is placed on a sheet of paper in any of its four possible orientations (rotating but not flipping), each cell of the sheet is exposed exactly once.
Here is an example of such a stencil:
To encrypt a text of N^2 characters, Petya follows this process: First, he writes the first N^2/4 characters of the text into the stencil's cut-out cells, filling them row by row from top to bottom and left to right within each row. For instance, if Petya encrypts the word "ОЛИМПИАДА", it is placed in the cells like this:
Next, he rotates the stencil 90 degrees clockwise and writes the next N^2/4 characters into the cut-out cells in the same manner. This process continues. If the text is shorter than N^2 characters, the remaining cells are left blank.
For example, encrypting the text "ОЛИМПИАДА ПО ИНФОРМАТИКЕ 2006 ГОДА" with the stencil proceeds as follows. The word "ОЛИМПИАДА" is encrypted first. For clarity, spaces are represented as underscores. On the second rotation, Petya encrypts "_ПО_ИНФОР":
On the third rotation, "МАТИКЕ_20" is encrypted:
On the fourth rotation, "06_ГОДА" is encrypted, with remaining cells left blank (spaces are denoted by underscores):
After completing this process, Petya compiles the encrypted text into a single line:
О М0ЛП6И МОАТГ ИПОИКИДНАДАЕФ О 2РА 0
To enhance security, Petya repeats the encryption process on the resulting text using the same stencil, and continues this cycle. To his surprise, after several repetitions, the encrypted text returns to its original form.
Your task is to write a program that determines the minimum number of encryption cycles needed for the text to revert to its original form, regardless of the text content.
Input
The input begins with the number N — the size of the stencil (2 ≤ N ≤ 150). This is followed by N^2 numbers (either 0 or 1), which describe the stencil. A 1 indicates a cut-out cell, while a 0 indicates a non-cut-out cell. It is guaranteed that the sequence describes a valid stencil for the encryption method.
Output
Output a single number — the minimum number of encryption repetitions required for the text to return to its original form, regardless of its content.