Harold 继承了一个拥有数百匹马的巨大栖息地！他想为一年两度的亚利桑那菲尼克斯无鞍牛仔（Bareback Arizona Phoenix Cowboys）活动训练几匹马，该活动旨在向亚利桑那州的骑马历史致敬。因此，Harold 为他的马匹报名了跨栏跳跃（Hurdle Hopping）项目，并请求你帮助他管理训练计划。

跨栏跳跃场地有许多种可能的布局，每种布局都需要一个不同的矩形区域。然而，栖息地中的土地并非都适合作为场地。此外，马匹需要在多个不同的场地上进行训练，以学会适应各种可能的情况。因此，在管理训练计划时，能够将场地重建在许多不同的位置是至关重要的。

你收到了一张地图，将栖息地表示为一个单位正方形网格，每个正方形表示该土地是否适合作为场地。请通过回答一系列问题来帮助 Harold，每个问题询问在栖息地中，特定尺寸的跨栏跳跃场地有多少个可能的放置位置。

Harold 希望他能放牧他引以为傲的马匹，就像 Ome Loeks 一样。CC BY-SA 3.0，由 Bouwe Brouwer 上传至维基共享资源

输入格式

输入包含以下内容：

• 第一行包含三个整数 $r$、$c$ 和 $q$（$1 \le r, c \le 9 \cdot 10^6$，$r \cdot c \le 9 \cdot 10^6$，$1 \le q \le 10^5$），分别表示网格的行数、列数以及询问的数量。
• 接下来的 $r$ 行，每行包含 $c$ 个字符。如果对应的方格表示适合作为场地的土地，则字符为 .；否则为 #。
• 接下来的 $q$ 行，每行包含两个整数 $h$ 和 $w$（$1 \le h \le r$，$1 \le w \le c$），表示 Harold 的一个询问，即网格中高度为 $h$（网格中的行数）且宽度为 $w$（网格中的列数）的跨栏跳跃场地的数量。

输出格式

对于 $q$ 个询问中的每一个，输出一个整数，表示与网格对齐、且尺寸为请求的高度 $h$（网格中的行数）和宽度 $w$（网格中的列数）的跨栏跳跃场地在网格中可能的放置位置数量。

样例

输入样例 1

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

输出样例 1

3

输入样例 2

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

输出样例 2

7
4
3
1
1
0

输入样例 3

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

输出样例 3

6
4
3
2
2
1

输入样例 4

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

输出样例 4

4
14
2
4
6