Texture Tile

Time limit2sMemory limit256 MB

Summary

Given an N x N image, find the largest square subimage whose top row equals its bottom row and left column equals its right column.

Level: Medium7 of 10
Topics: Dynamic programming, Hash map, Binary search
Solved: No attempts yet

Problem

A square raster image is represented by an $N \times N$ array of pixels. A texture tile is a square (sub)image whose first row is identical to its last row and whose first column is identical to its last column. This property is useful when covering the surface of a graphics object with repeated copies of a texture, because it lets adjacent copies join together "seamlessly".

Given an image, find the side length of the largest square subimage that is a texture tile.

Input

The first token is the integer $N$ . It is followed by $N^2$ integers $c_{i,j}$ , the pixel values, given row by row (row $1$ first, then row $2$ , and so on).

Output

Print a single integer $m$ : the side length of the largest texture tile contained in the image. (Since a single pixel is always a texture tile, $m \ge 1$ always holds.)

Constraints

$1 \le N \le 370$
$0 \le c_{i,j} \le 255$

Examples4

Example 1
Input
```
2
0 0
2 3
```
Expected output
```
1
```
Example 2
Input
```
4
1 0 0 0
1 2 5 2
1 0 0 0
4 4 4 4
```
Expected output
```
3
```
Example 3
Input
```
1
5
```
Expected output
```
1
```
Example 4
Input
```
2
5 5
5 5
```
Expected output
```
2
```