男孩 Smilo 正在玩 Minecraft!为了准备与巨龙的战斗,他需要大量的金苹果,为此,他需要大量的黄金。因此,斯米洛去了矿井。
矿井是一个大小为 $$$n \times m$$$ 的矩形网格,其中每个单元格可以是金矿石、石头或空单元格。斯米洛可以炸毁任何空牢房中的炸药。当炸药在坐标为 $$$(x, y)$$$ 的空单元格中爆炸时,以单元格 $$$(x, y)$$$ 为中心、边长 $$$2k + 1$$$ 的正方形内的所有单元格都会变空。如果找到金矿石 严格在里面 这个正方形(不在边界上),它消失了。然而,如果金矿石位于该正方形的边界上,斯米洛就会收集该金子。
炸药只能在矿井内引爆,但爆炸方块可以延伸到矿井边界之外。
确定 Smilo 可以收集的最大金币数量。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1 \leq n, m, k \leq 500$$$) — 分别是行数、列数和爆炸参数 $$$k$$$。
以下 $$$n$$$ 行均包含 $$$m$$$ 个字符,每个字符等于 '.', '#',或 'g',其中 '.' — 是一个空单元格, '#' — 是石头, 'g' — 是黄金。保证至少有一个单元格是空的。
保证所有测试用例的总和 $$$n \cdot m$$$ 不超过 $$$2.5 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数——可以获得的最大黄金数量。
示例
输入复制
32 3 1#.#g.g2 3 2#.#g.g3 4 2.gg.g..#g##.
输出复制
2 0 4
注意
在第一个测试用例中,Smilo 可以引爆任何空单元格中的炸药并获得 $$$2$$$ 金币:
在第二个测试用例中,无论Smilo做什么,他都无法获得任何金币:
在第三个测试用例中,可以引爆右下角的炸药以获得$$$2$$$金币,然后在左侧一个单元格再次爆炸以获得剩余的$$$2$$$金币: