题目描述

Igor 在博物馆中，他希望看到尽可能多的图片。

博物馆可以表示为一个 $n \times m$ 的矩形网格。每个单元格要么是空的，要么是不可通行的。空单元格用 . 标记，不可通行的单元格用 * 标记。每两个相邻的不同类型的单元格（一个空单元格和一个不可通行单元格）之间被一堵墙隔开，墙上有一幅图片。

开始时，Igor 位于某个空单元格中。在任意时刻，他可以移动到与当前单元格共享一条边的任何空单元格。

对于多个起始位置，你需要计算 Igor 能够看到的最大图片数量。只有当 Igor 位于与带有图片的墙相邻的单元格时，他才能看到该图片。Igor 有充足的时间，因此他会检查所有能看到的图片。

输入格式

输入的第一行包含三个整数 $n , m , k$（$3 \le n, m \le 1000 ,1 \le k \le \min(nm, 100000)$）——博物馆的尺寸和需要处理的起始位置数量。

接下来的 $n$ 行，每行包含 $m$ 个符号 . 或 *——表示博物馆的描述。保证所有边界单元格都是不可通行的，因此 Igor 无法离开博物馆。

最后 $k$ 行，每行包含两个整数 $x$ 和 $y$（$1 \le x \le n$, $1 \le y \le m$）——分别表示 Igor 的起始位置的行和列。行从上到下编号，列从左到右编号。保证所有起始位置都是空单元格。

输出格式

输出 $k$ 个整数——表示 Igor 从对应起始位置开始能够看到的最大图片数量。

样例

5 6 3
******
*..*.*
******
*....*
******
2 2
2 5
4 3

6
4
10

4 4 1
****
*..*
*.**
****
3 2

8

数据范围