Pusheen has received a present from her friend! It turns out to be a puzzle similar to the 15-puzzle.

The puzzle is an $N\times N$ grid where each integer from $1$ to $N^2$ appears on the grid exactly once. In one move, Pusheen can take any $K\times K$ subgrid and rotate it in place by 90 degrees, either clockwise or counter-clockwise. $K$ can vary from move to move. The goal is for the integers to be in sorted order when read in row-major order - that is to say, each row is in sorted order, each column is in sorted order, and if the integers are read in order from the first row to the last row, going from left to right, the integers form the sequence $1$ to $N^2$.

Pusheen is getting started on this puzzle, and has it set to the Easy difficulty. On Easy difficulty, Pusheen is able to solve the puzzle by rotating exactly one subgrid by 90 degrees. Help Pusheen determine the size of the subgrid she should rotate.

Constraints

$2\le N\le {10}^3$

In tests worth 1 mark, $N=2$.

In additional tests worth 2 marks, $N\le 3$.

In additional tests worth 11 marks, $N\le 20$.

Input Specification

The first line of input is a single positive integer, $N$.

The next $N$ lines each contain $N$ space-separated positive integers. These lines define the arrangement of numbers on the grid.

Output Specification

Output, on a single line, the size of the subgrid Pusheen will rotate. It is guaranteed that this integer will be at least 2, and will be unique.

Sample Input

3
1 2 3
4 8 5
7 9 6

Sample Output

2