Mine the Gradient

To prepare for a possible alien invasion, we first have to find out where the aliens might come from. One way to tell whether a planet is inhabited by intelligent creatures is to study high-resolution pictures of the planet and look for the tell-tale effects of intelligent life. Because there are so many candidate planets, this search has to be done by a computer program.

One distinctive feature of a colonized planet is the presence of surface mines. A mine is a square structure whose depth decreases uniformly from one side of the square toward the opposite side. On a grayscale image it therefore shows up as a square whose shade is either constant or changes gradually and uniformly from one side to another.

Your task is to find the largest mine on a grayscale bitmap of a planet. The picture is a rectangular grid of integers between $0$ and $65535$, where $A_{i,j}$ is the shade of grey of the pixel in row $i$ and column $j$. Only square mines in a few special orientations are considered.

An axis-parallel square of side $L$ is the block of pixels $A_{i,j}$ with $r \le i \le r+L-1$ and $c \le j \le c+L-1$.

Such a square is a mine if there exist integers $S$ and $K$ for which its shades follow one of the following four gradient patterns:

• row gradient (vertical mine): $A_{i,j} = S + iK$ — the shade depends only on the row;
• column gradient (horizontal mine): $A_{i,j} = S + jK$ — the shade depends only on the column;
• diagonal gradient: $A_{i,j} = S + (i + Qj)K$ for some $Q \in \{+1, -1\}$ — the shade stays constant along one of the two diagonal directions.

A single pixel is always a (degenerate) mine.

The input contains several pictures. Each picture begins with a line containing two integers $N$ and $M$ ($1 \le N, M \le 2000$), the height and the width of the picture. The next $N$ lines contain $M$ integers each: the $j$-th integer on the $i$-th of these lines is $A_{i,j}$ ($0 \le A_{i,j} \le 65535$), the shade of the pixel in row $i$ and column $j$. Integers on a line are separated by at least one space; there may be extra spaces between the numbers and also at the beginning or the end of a line.

The list of pictures ends with a line containing two zeros, which is not a picture and must not be processed.

For each picture, output a single line containing one integer: the area (the number of pixels) of the largest row-gradient, column-gradient, or diagonal mine in that picture.