Paint by Letters

Bessie has recently received a painting set. The canvas is an $N \times M$ rectangle of cells. Rows are numbered $1\ldots N$ from top to bottom, and columns are numbered $1\ldots M$ from left to right ($1\le N,M\le 1000$). Once painted, a cell gets one uppercase letter from 'A' to 'Z' as its color. Initially, all cells are uncolored, and a cell cannot be painted more than once.

Bessie has chosen the desired color for each cell. She can paint a set of cells with one color in a single stroke if the set forms a connected component, that is, any cell in the set can reach any other through a sequence of adjacent cells. Two cells are adjacent if they share an edge.

For example, the $3 \times 3$ canvas below can be colored in four strokes.

AAB
BBA
BBB

...    ..B    AAB    AAB    AAB
... -> ... -> ... -> BB. -> BBA
...    ...    ...    BBB    BBB

Fewer than four strokes cannot produce the result.

Bessie is an avant-garde artist, so she paints only a subrectangle of the canvas. She is considering $Q$ candidates ($1\le Q\le 1000$). Each candidate is given by four integers $x_1$, $y_1$, $x_2$, and $y_2$, and it denotes the subrectangle of all cells with row in the range $x_1$ to $x_2$ inclusive and column in the range $y_1$ to $y_2$ inclusive.

For each candidate, find the minimum number of strokes needed to paint every cell in the subrectangle with its desired color while leaving all cells outside the subrectangle uncolored. Bessie does not actually paint anything during this process, so the answers for the candidates are independent of each other.

The first line contains $N$, $M$, and $Q$.

Each of the next $N$ lines contains a string of $M$ uppercase letters, giving the desired colors for one row of the canvas.

Each of the next $Q$ lines contains four space-separated integers $x_1$, $y_1$, $x_2$, and $y_2$, describing one candidate subrectangle ($1\le x_1\le x_2\le N$, $1\le y_1\le y_2\le M$).

For each of the $Q$ candidates, print the answer on its own line.