题目描述

你正在筹备一场甜品派对，场地是一个 $H$ 行 $W$ 列的方形甜品区，每个区域有三种状态：

• #：该区域是装饰性蛋糕摆件（障碍物），无法通行也无法被巧克力灌溉
• .：该区域是可摆放小甜点的空台
• H：该区域安装了巧克力喷泉

巧克力喷泉会向四周（上、下、左、右四联通方向）喷洒巧克力，定义一个空台是被巧克力覆盖的，当且仅当从某个巧克力喷泉出发，通过最多 $D$ 步移动（每一步只能走四联通方向，且不能穿过装饰性蛋糕摆件）可以到达该区域。 注意，巧克力喷泉所在的区域本身也视为被巧克力覆盖的。

请你计算这个甜品区中有多少块被巧克力覆盖的区域。

输入格式

第一行三个整数 $H,W,D$，分别表示甜品区的行数、列数和步数；

接下来 $H$ 行，每行 $W$ 个字符，描述甜品区的区域状态。

输出格式

输出一个整数，表示被巧克力覆盖的区域总数。

输入输出样例

3 4 1
H...
#..H
.#.#

5

5 6 2
##...H
H.....
..H.#.
.HH...
.###..

21

1 6 3
...#..

0

样例解释1

甜品区中坐标为 $(1,1),(1,2),(1,4),(2,3),(2,4)$ 的区域是被巧克力覆盖的（坐标从1开始计数）。

样例解释3

甜品区中没有安装任何巧克力喷泉，因此没有被巧克力覆盖的区域，输出 0。

说明/提示

• $1\le H,W\le1000$
• $1\le D\le H\times W$