Largest Square Killer

Time limit5sMemory limit128 MB

Summary

Given an R x C binary grid, find the side length of the largest square submatrix that remains unchanged after a 180 degree rotation.

Level: Medium7 of 10
Topics: String matching, Binary search, Matrix, Implementation
Solved: No attempts yet

Problem

Program memory is an R x C matrix made of 0s and 1s. A square submatrix is called a Square Killer if rotating that submatrix by 180 degrees leaves every entry exactly the same.

The size of a square is the number of cells on one side. Find the largest possible size of a Square Killer in the given memory.

Input

The first line contains R and C. Both values are positive integers at most 300. The next R lines each contain a string of length C. Every character is either 0 or 1.

Output

Print the size of the largest Square Killer.

Hint

In the given grid, (1,5)-(2,6), (2,4)-(3,5), and (1,1)-(3,3) are all Square Killers. Among them, (1,1)-(3,3) is the largest, with size 3.

Examples1

Example 1
Input
```
3 6
101010
111001
101001
```
Expected output
```
3
```