CF598D Igor In the Museum

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 从对应起始位置开始能够看到的最大图片数量。