伊戈尔在博物馆里,他想看尽可能多的照片。
博物馆可以表示为一个由 n × m 个单元组成的矩形区域。每个牢房要么是空的,要么是无法通行的。空单元格用“.”标记,不可通过的单元格用“*”标记。每两个不同类型的相邻牢房(一个是空的,一个是不可通行的)被一面包含一张图片的墙隔开。
一开始,伊戈尔在某个空牢房里。他随时都可以移动到与当前单元格共享一侧的任何空单元格。
对于几个起始位置,您应该计算 Igor 可以看到的最大图片数量。只有当伊戈尔位于靠近有这张照片的墙壁的牢房中时,他才能看到这张照片。伊戈尔有很多时间,所以他会检查他能看到的每一张图片。
输入
输入的第一行包含三个整数 n、m 和 k (3 ≤ n, m ≤ 1000, 1 ≤ k ≤ min(n·m, 100 000)) - 博物馆尺寸和要处理的起始位置的数量。
接下来的 n 行每一行都包含 m 个符号“.”、“*”——博物馆的描述。保证所有边境牢房都无法通行,所以伊戈尔无法走出博物馆。
最后 k 行中的每一行包含两个整数 x 和 y (1 ≤ x ≤ n, 1 ≤ y ≤ m)——分别是 Igor 起始位置之一的行和列。行从上到下编号,列从左到右编号。保证所有起始位置都是空单元格。
输出
打印 k 个整数 — 如果 Igor 从相应的位置开始,他可以看到的最大图片数。
示例
输入 #1
5 6 3 ****** *..*.* ****** *....* ****** 2 2 2 5 4 3
输出 #1
6 4 10
输入 #2
4 4 1 **** *..* *.** **** 3 2
输出 #2
8