Debug

Time limit5sMemory limit128 MB

Summary

Given a binary R by C grid, find the largest square submatrix (side at least 2) that is invariant under 180-degree rotation, or output -1.

Level: Medium5 of 10
Topics: Dynamic programming, Matrix, Brute force
Solved: No attempts yet

Problem

While debugging a program, Sanggeun noticed that certain square patterns in program memory are closely related to bugs.

Program memory is an R by C matrix consisting only of 0 and 1.

A square killer is a square submatrix larger than one character that stays exactly the same after being rotated by 180 degrees. In other words, for a square killer of size K, every character at (i, j) from the top-left corner is equal to the character at the symmetric position (K-1-i, K-1-j) from the top-left corner.

Given the program memory, find the size of the largest square killer. The size of a square killer is both its number of rows and its number of columns.

Input

The first line contains natural numbers R and C, each at most 300.

Each of the next R lines contains a string of length C. Every character is either 0 or 1, with no spaces between characters.

Output

Print the size of the largest square killer.

If there is no square killer, print -1.

Examples3

Example 1
Input
```
3 6
101010
111001
101001
```
Expected output
```
3
```
Example 2
Input
```
4 5
10010
01010
10101
01001
```
Expected output
```
3
```
Example 3
Input
```
3 3
101
111
100
```
Expected output
```
-1
```