C. Smilo和我的世界
每个测试的时间限制：2 秒
内存限制：256 兆字节

男孩 Smilo 正在玩《我的世界》！为了与末影龙战斗，他需要很多金苹果，而金苹果需要很多金锭。因此，Smilo 前往矿洞。

矿洞是一个大小为 $n \times m$ 的矩形网格，每个格子可能是金矿石、石头或空单元格。Smilo 可以在任意一个空单元格引爆炸药。当炸药在坐标 $(x, y)$ 的空单元格爆炸时，所有位于以 $(x, y)$ 为中心、边长为 $2k+1$ 的正方形内部的格子都会变为空单元格。如果金矿石位于这个正方形的严格内部（不包含边界），它会消失；而如果金矿石位于这个正方形的边界上，Smilo 则会收集到这些金矿石。

炸药只能在矿洞内部引爆，但爆炸产生的正方形可以延伸到矿洞的边界之外。

请确定 Smilo 最多可以收集到的金矿石数量。

输入
每个测试文件包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含三个整数 $n$、$m$ 和 $k$（$1 \le n, m, k \le 500$），分别表示行数、列数和爆炸参数 $k$。

接下来的 $n$ 行，每行包含 $m$ 个字符，每个字符是以下之一：

• '.' 表示空单元格
• '#' 表示石头
• 'g' 表示金矿石

保证至少有一个单元格是空单元格。

另外，所有测试用例的 $n \cdot m$ 之和不超过 $2.5 \cdot 10^5$。

输出
对于每个测试用例，输出一个整数，表示 Smilo 最多能收集到的金矿石数量。

示例

输入：

3
2 3 1
#.#
g.g
2 3 2
#.#
g.g
3 4 2
.gg.
g..#
g##.

输出：

2
0
4

注释

• 在第一个测试用例中，Smilo 可以在任意空单元格引爆炸药并获得 $2$ 块金矿石。
• 在第二个测试用例中，无论怎么做，都无法获得任何金矿石。
• 在第三个测试用例中，可以首先在右下角引爆炸药获得 $2$ 块金矿石，然后再向左一格引爆炸药，获得剩下的 $2$ 块金矿石。