B. 矿石采集

题目描述

男孩斯米洛正在玩《我的世界》！为了准备与末影龙的战斗，他需要大量金苹果，因此急需黄金。斯米洛决定前往矿洞开采。

矿洞是一个大小为 $n \times m$ 的矩形网格，每个单元格可能是金矿石（g）、岩石（#）或空地（.）。斯米洛可以在任意空地单元格引爆炸药。当坐标为 $(x, y)$ 的空地发生爆炸时，会形成一个以该点为中心、边长为 $2k + 1$ 的正方形区域。爆炸效果如下：

• 正方形边界上的金矿石会被斯米洛收集（消失并计入黄金）。
• 正方形内部（非边界）的金矿石会直接消失（不被收集）。
• 爆炸范围允许超出矿洞边界，但炸药只能在矿洞内的空地引爆。

已知至少有一个空地单元格。请计算斯米洛能收集的最大黄金量（即边界金矿石的最大数量）。

输入格式

第一行输入整数 $t$，表示测试用例数量。

对于每个测试用例，第一行输入三个整数 $n$，$m$，$k$。接下来 $n$ 行，每行 $m$ 个字符（仅含 .，#，g），只要有一块空地。

输出格式

每个测试用例输出一个整数，表示最大可收集的黄金量。

样例输入1

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

样例输出1

2
0
4

数据范围

• 对于 $10\%$ 的数据，有 $1 \le n, m, k \le 10$。
• 对于 $30\%$ 的数据，有 $1 \le \sum n \times m \le 100$，$1 \le n, m, k \le 100$。
• 对于 $100\%$ 的数据，有 $1 \le \sum n \times m \le 2 \times 10^5$，$1 \le n, m, k \le 500$。