该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

江桥的花园可以看成是 $n$ 行 $m$ 列的网格，从上到下第 $i$ 行，从左到右第 $j$ 行的格子为 $(i,j)$。每个格子里都有一朵花，有的花开了有的花没开，开了的用 * 表示，没开的用 . 表示。

称一片 花海 为：只包含已经开了的花朵的连通区域。这里的连通指的是四连通，即花海内任意一朵花朵都可以通过上下左右移动且只经过已经开了的花朵就可以到达花海内任意一个其他的开花的位置。

现在江桥可以使用恰好一次 “开花药水”，即选中某个格子 $(i,j)$ ，使得第 $i$ 行和第 $j$ 列的所有花朵开放。

现在有 $q$ 次询问，每次询问给出 $x,y$，表示查询如果在 $(x,y)$ 处使用 “开花药水”，所能形成的最大的花海的面积是多少（花海的面积即为花海所包含的花朵数目）。

输入格式

从文件 bloom.in 读入数据。 第一行三个正整数 $n,m,q$，表示花园的行数、列数、询问次数。

接下来 $n$ 行每行一个长度为 $m$ 的字符串 $s_i$，表示这一行的所有花朵的开花状态。

接下来 $q$ 行，每行 $2$ 个整数 x y，表示一组询问。

输出格式

输出到文件 bloom.out。 $q$ 行每行一个非负整数，表示答案。

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

14
10
15

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

18
18
18
17
17

样例 3

见 bloom3.in 与 bloom3.ans。

样例 4

见 bloom4.in 与 bloom4.ans。

样例 5

见 bloom5.in 与 bloom5.ans。

样例 6

见 bloom6.in 与 bloom6.ans。

样例 7

见 bloom7.in 与 bloom7.ans。

数据规模与约定

下发文件分别对应子任务 $1,2,3,4,5$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $1 \leq n,m \leq 2 \times 10^{3}$，$1 \leq q \leq 10^{6}$，$1 \leq x \leq n$，$1 \leq y \leq m$，且 $s_{i,j}$ 只可能是 '.' 或 '*'。

时空限制：$1$ 秒 / $256\,\mathrm{MiB}$。