Maximum Monochrome Staircase

Small Blue loves staircase patterns. A staircase pattern of size $N$ is defined as an arrangement of $N$ columns placed side‐by‐side, where the $i$-th column contains exactly $i$ identical squares (i.e. same size and color) for $1 \le i \le N$. When the bottoms of the columns are aligned, a staircase pattern is formed. Furthermore, any pattern obtained by rotating a staircase pattern by a multiple of $90^\circ$ is still considered a staircase pattern. For example, the following four orientations are valid for a staircase pattern of size $N$:

1., 0° rotation (original): In an $N\times N$ box with rows indexed $0$ to $N-1$ from top to bottom and columns $0$ to $N-1$, the cell at position $(i,j)$ is included if [ i \ge N - j - 1. ]

2., 90° rotation: In an $N\times N$ box, the cell at position $(i,j)$ is included if [ i \ge j. ]

3., 180° rotation: In an $N\times N$ box, the cell at position $(i,j)$ is included if [ i \le N - j - 1. ]

4., 270° rotation: In an $N\times N$ box, the cell at position $(i,j)$ is included if [ i \le j. ]

Small Blue has a cloth divided into an $H \times H$ grid. Each cell of the grid has its own color (represented by an integer). He can cut the cloth along the cell boundaries to obtain a piece exactly in the shape of a staircase pattern (in any one of the four allowed rotations). What is the maximum staircase size $N$ such that there exists a staircase pattern formed by cells of a single color that can be cut out from the cloth?

inputFormat

The first line of input contains a single integer $H$ ($1 \le H \le 50$), the size of the cloth. Each of the next $H$ lines contains $H$ integers separated by spaces, where each integer represents the color of that cell.

outputFormat

Output a single integer, the maximum size $N$ of a monochrome staircase pattern that can be obtained from the cloth. If no staircase pattern (even of size 1) exists, output 0.

sample

3
1 1 1
1 1 1
1 1 1

3