CF598D.Igor In the Museum

Igor is in the museum and he wants to see as many pictures as possible.

Museum can be represented as a rectangular field of n × m cells. Each cell is either empty or impassable. Empty cells are marked with '.', impassable cells are marked with '*'. Every two adjacent cells of different types (one empty and one impassable) are divided by a wall containing one picture.

At the beginning Igor is in some empty cell. At every moment he can move to any empty cell that share a side with the current one.

For several starting positions you should calculate the maximum number of pictures that Igor can see. Igor is able to see the picture only if he is in the cell adjacent to the wall with this picture. Igor have a lot of time, so he will examine every picture he can see.

伊戈尔正在博物馆中参观，他希望尽可能多地观赏画作。

博物馆可以表示为一个 $n \times m$ 的矩形网格。每个格子要么为空（可通行），要么为障碍（不可通行）。空格子用字符 . 表示，障碍格子用字符 * 表示。任意两个相邻（共享一条边）且类型不同的格子（一个为空，另一个为障碍）之间都有一堵墙，墙上恰好挂着一幅画。

初始时，伊戈尔位于某个空格子中。在任意时刻，他都可以移动到与当前格子共享一条边的任意一个空格子中。

对于若干个给定的起始位置，请分别计算伊戈尔最多能够看到多少幅画。伊戈尔仅当处于与挂有某幅画的墙相邻的格子中时，才能看到该画。伊戈尔有充足的时间，因此他会仔细查看所有他能看到的画。

First line of the input contains three integers n, m and k (3 ≤ n, m ≤ 1000, 1 ≤ k ≤ min(n·m, 100 000)) — the museum dimensions and the number of starting positions to process.

Each of the next n lines contains m symbols '.', '*' — the description of the museum. It is guaranteed that all border cells are impassable, so Igor can't go out from the museum.

Each of the last k lines contains two integers x and y (1 ≤ x ≤ n, 1 ≤ y ≤ m) — the row and the column of one of Igor's starting positions respectively. Rows are numbered from top to bottom, columns — from left to right. It is guaranteed that all starting positions are empty cells.

输入的第一行包含三个整数 $n$、$m$ 和 $k$（$3 \leq n, m \leq 1000$，$1 \leq k \leq \min(n\cdot m,\,100\,000)$）——分别表示博物馆的尺寸以及需要处理的起始位置数量。

接下来的 $n$ 行，每行包含 $m$ 个字符，为 '.' 或 '*' —— 描述博物馆的布局。保证所有边界格子均不可通行，因此 Igor 无法离开博物馆。

最后的 $k$ 行，每行包含两个整数 $x$ 和 $y$（$1 \leq x \leq n$，$1 \leq y \leq m$）—— 分别表示 Igor 的一个起始位置所在的行号与列号。行号从上到下编号，列号从左到右编号。保证所有起始位置均为可通行的空单元格（即 '.'）。

Print k integers — the maximum number of pictures, that Igor can see if he starts in corresponding position.

输出 k 个整数——即 Igor 从对应位置出发时，能够看到的最多图片数量。