题目描述

波在不同的介质中的传播速度是不一样的。真空中波速都是3*108m/s，而在液体介质中的波速会比真空中的波速小，并且在不同的液体介质中波速不一样。我们将一个液体表面分成N * M块相同大小的正方形格子，每个格子中只包含一种液体介质。现在我们想知道，从某个波源传出去的波能以不变的波速延伸到多大的以波源为中心的大正方形内。假定所有大正方形的边都是平行于坐标轴的。

输入格式：

输入文件第一行包含三个整数N、M和Q，分别表示液体表面分成的正方形格子的行数和列数，以及询问的个数。接下来是一个N * M的矩阵，其中每个元素包含一个小写字母表示相应各自内的介质，不同的字母表示不同的介质。接下来Q行每行用两个数X和Y描述一个询问，表示询问以第X行第Y列为波源的波能以不变的波速延伸到的最大的以波源为中心的大正方形的边长。注意行的标号从0到N-1，列的标号从0到M-1。

输出格式：

输出文件包括Q行，每行包含一个整数，即相应问题的答案。

输入样例#1：

5 5 3
abbaa
abbaa
aaaaa
aaaaa
aaaaa
1 2
1 4
3 2

输出样例#1：

1
1
3

说明/提示

对于30%的数据，有1 ≤ N,M ≤ 50，1 ≤ Q ≤ 500；

对于100%的数据，有1 ≤ N,M≤ 1000，1 ≤ Q ≤ 10000。