Bessie 最近收到了一套绘画工具。画布可以表示为一个 $N \times M$ 的矩形网格，行从上到下编号为 $1\ldots N$，列从左到右编号为 $1\ldots M$ ($1\le N,M\le 1000$)。一旦涂色，单元格的颜色可以用 'A' 到 'Z' 的大写字母表示。最初，所有单元格均未涂色，且每个单元格只能涂色一次。

Bessie 已经指定了每个单元格所需的颜色。如果一组单元格形成一个连通分量（即集合中的任意两个单元格都可以通过一系列相邻单元格相互到达），她可以用一笔涂完这组相同颜色的单元格。如果两个单元格共享一条边，则认为它们是相邻的。

例如，$3\times 3$ 的画布

AAB
BBA
BBB

可以用四笔涂完，过程如下：

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

无法用少于四笔的结果完成。

作为一名先锋艺术家，Bessie 最终只会涂抹画布的一个子矩形。目前，她正在考虑 $Q$ 个候选方案 ($1\le Q\le 1000$)，每个方案由四个整数 $x_1, y_1, x_2, y_2$ 表示。这意味着子矩形由行范围在 $x_1$ 到 $x_2$（含）之间、列范围在 $y_1$ 到 $y_2$（含）之间的所有单元格组成。

对于每个候选子矩形，将子矩形内的每个单元格涂上其所需颜色，同时保持子矩形外的所有单元格不涂色，最少需要多少笔？注意，Bessie 在此过程中实际上并没有进行任何涂色，因此每个候选方案的答案是独立的。

注意：本题的时间限制比默认值高 50%，内存限制为 512MB，是默认值的两倍。

输入格式

第一行包含 $N, M, Q$。

接下来的 $N$ 行，每行包含一个长度为 $M$ 的大写字母字符串，表示画布每一行所需的颜色。

接下来的 $Q$ 行，每行包含四个空格分隔的整数 $x_1, y_1, x_2, y_2$，表示一个候选子矩形 ($1\le x_1\le x_2\le N$, $1\le y_1\le y_2\le M$)。

输出格式

对于每个候选方案，输出一行答案。

样例

样例输入 1

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

样例输出 1

6
3
2
1
4
1
3
2
2

第一个候选方案由整个画布组成，可以用六笔涂完。

第二个候选方案由所需颜色为

ABBA

的子矩形组成，可以用三笔涂完。注意，虽然如果考虑整个画布，$(3,5)$ 和 $(3,8)$ 处的单元格可以用 'A' 一笔涂完，但在仅考虑子矩形内的单元格时并非如此。

子任务

• 测试点 1-2 满足 $N,M\le 50$。
• 在测试点 3-5 中，画布不包含任何单一颜色的环。也就是说，不存在由不同单元格组成的序列 $c_1,c_2,c_3,\ldots,c_k$ 满足以下所有条件：
  • $k>2$
  • $c_1,\ldots,c_k$ 的所需颜色全部相同。
  • 对于每个 $1\le i
  • $c_k$ 与 $c_1$ 相邻。

  注意，上述 $3\times 3$ 画布包含一个单一颜色的环（左下角的四个 B）。

• 在测试点 6-8 中，每个由相同颜色单元格组成的连通分量都可以包含在一个边平行于坐标轴的 $2\times 2$ 正方形内。上述 $3\times 3$ 画布不满足此属性（包含五个 B 的连通分量无法包含在 $2\times 2$ 正方形内）。
• 在测试点 9-11 中，每个由相同颜色单元格组成的连通分量都可以包含在一个边平行于坐标轴的 $3\times 3$ 正方形内。上述 $3\times 3$ 画布满足此属性。
• 测试点 12-20 满足无额外限制。