题目背景

Harold 继承了一片巨大的马匹栖息地，并打算训练其中一些马参加 Hurdle Hopping 跨栏活动。

不同的训练路线需要不同大小的矩形场地，而栖息地中的部分土地并不适合修建训练场。为了让马匹适应不同环境，Harold 希望知道：对于指定的场地尺寸，栖息地中一共有多少个可用位置。

题目描述

给定一个由 $r$ 行 $c$ 列单位方格组成的网格：

• . 表示该方格适合修建训练场；
• # 表示该方格不适合修建训练场。

一块训练场必须满足：

• 与网格坐标轴平行；
• 恰好覆盖一个 $h\times w$ 的矩形区域；
• 所覆盖的所有方格均为 .。

接下来有 $q$ 个询问。每个询问给出训练场的高度 $h$ 和宽度 $w$，你需要计算网格中有多少个不同的位置可以放置这样的训练场。

两个位置只要覆盖的方格集合不同，就视为不同。

输入格式

第一行包含三个整数 $r,c,q$：

$$1\le r,c\le 9\times 10^6, \qquad r\cdot c\le 9\times 10^6, \qquad 1\le q\le 10^5.$$

接下来 $r$ 行，每行包含一个长度为 $c$ 的字符串，仅由 . 和 # 组成，表示网格。

接下来 $q$ 行，每行包含两个整数 $h,w$（$1\le h\le r$，$1\le w\le c$），表示一次询问。

输出格式

对于每次询问，输出一行一个整数，表示网格中完全由 . 构成的 $h\times w$ 轴对齐矩形数量。

样例 1

输入

1 7 1
#....#.
1 2

输出

3

样例 2

输入

3 3 6
..#
#..
...
1 1
1 2
2 1
3 1
2 2
3 3

输出

7
4
3
1
1
0

样例 3

输入

2 3 6
...
...
1 1
1 2
2 1
2 2
1 3
2 3

输出

6
4
3
2
2
1

样例 4

输入

3 5 5
.....
..#..
.....
2 2
1 1
1 5
3 1
1 3

输出

4
14
2
4
6