Bessie has recently received a painting set. The canvas can be represented as an N×MN×M rectangle of cells where the rows are labeled 1…N1…N from top to bottom and the columns are labeled 1…M1…M from left to right (1≤N,M≤10001≤N,M≤1000). Once painted, the color of a cell can be represented by an uppercase letter from 'A' to 'Z.' Initially, all cells are uncolored, and a cell cannot be painted more than once.Bessie has specified the color that she desires for each cell. She can paint a set of cells with a single color in one stroke if the set forms a connected component, meaning that any cell in the set can reach any other via a sequence of adjacent cells. Two cells are considered to be adjacent if they share an edge.

For example, the 3×33×3 canvas

AAB
BBA
BBB

can be colored in four strokes as follows:

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

It is not possible to produce the end result using less than four strokes.

Being an avant-garde artist, Bessie will end up painting only a subrectangle of the canvas. Currently, she is considering QQ candidates (1≤Q≤10001≤Q≤1000), each of which can be represented by four integers x1x1, y1y1, x2x2, and y2**.**y2. This means that the subrectangle consists of all cells with row in the range x1x1 to x2x2 inclusive and column in the range y1y1 to y2y2 inclusive.

For each candidate subrectangle, what is the minimum number of strokes needed to paint each cell in the subrectangle with its desired color while leaving all cells outside the subrectangle uncolored? Note that Bessie does not actually do any painting during this process, so the answers for each candidate are independent.

Note: The time limit for this problem is 50 percent higher than the default, and the memory limit is 512MB, twice the default.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains NN, MM, and QQ.The next NN lines each contain a string of MM uppercase characters representing the desired colors for each row of the canvas.

The next QQ lines each contain four space-separated integers x1**,y1**,x2**,y2x1,y1,x2,y2 representing a candidate subrectangle (1≤x1≤x2≤N1≤x1≤x2≤N, 1≤y1≤y2≤M**1≤y1≤y2≤M).

OUTPUT FORMAT (print output to the terminal / stdout):

For each of the QQ candidates, output the answer on a new line.

SAMPLE INPUT:

4 8 9
ABBAAAAA
ABAAAABA
CAADABBA
AAAAAAAA
1 1 4 8
3 5 3 8
1 3 2 4
1 4 2 5
1 1 3 3
4 4 4 4
2 6 4 8
3 5 4 6
1 6 3 8

SAMPLE OUTPUT:

6
3
2
1
4
1
3
2
2

The first candidate consists of the entire canvas, which can be painted in six strokes.

The second candidate consists of the subrectangle with desired colors

ABBA

and can be colored in three strokes. Note that although the cells at (3,5)(3,5) and (3,8)(3,8) can be colored with AA in a single stroke if you consider the entire canvas, this is not the case when considering only the cells within the subrectangle.

SCORING:

• Test cases 1-2 satisfy N,M≤50N,M≤50.

• In test cases 3-5, the canvas contains no cycles of a single color. That is, there does not exist a sequence of distinct cells c1**,c2**,c3**,…,ck**c1,c2,c3,…,ck such that all of the following conditions are satisfied:

  • k>2k>2
  • All of c1**,…,ck**c1,…,ck have the same desired color.
  • cici is adjacent to ci**+1ci+1 for each 1≤i**<k1≤i<k.
  • ckck is adjacent to c1c1.

  Note that the 3×33×3 canvas above contains a cycle of a single color (the four Bs in the bottom-left corner).

• In test cases 6-8, every connected component consisting of cells with the same desired color can be contained within a two by two square with sides parallel to the coordinate axes. The 3×33×3 canvas above does not satisfy this property (the connected component with five Bs cannot be contained within a two by two square).

• In test cases 9-11, every connected component consisting of cells with the same desired color can be contained within a three by three square with sides parallel to the coordinate axes. The 3×33×3 canvas above satisfies this property.

• Test cases 12-20 satisfy no additional constraints.