CF2113C Smilo and Minecraft

Smilo 在玩 Minecraft！为了准备去打龙，他需要大量的金苹果，所以他需要大量的金子。因此，Smilo 准备下矿。 矿洞是一个 $n\times m$ 的矩形网格，每个格子可能是金矿、石头或空地。Smilo 可以在一个空地点燃炸药，这会将以此空地为中心的边长为 $2k+1$ 的正方形区域夷为平地。如果一个金矿在正方形的内部并且没有和边框相接触，那么它会直接消失；如果金矿在正方形的边框上（在内部并且和正方形的边相接触），Smilo 将会获得这个金子。 求出 Smilo 最多可以获得多少金子。

多组数据。第一行一个整数 $t(1\le t\le 10^4)$ 表示数据组数。 对于每组数据，第一行三个整数 $n,m,k(1\le n,m,k\le 500)$。\ 接下来 $n$ 行，每行一个由 `g`，`#` 和 `.` 构成的长度为 $m$ 的字符串，表示矿洞。`g` 表示金矿，`#` 表示石头，`.` 表示空格。 保证单个测试点中 $\sum nm\le 2.5\times 10^5$。

对于每组数据，输出一行一个整数表示答案。

**样例解释** 对于第一组数据，Smilo 可以在任意空地中引爆炸药获得 $2$ 个金子：  对于第二组数据，Smilo 怎么做都不能获得任何金子：  对于第三组数据，Smilo 可以先在左下角的空地中引爆炸药获得 $2$ 个金子，再在左边一个格子引爆炸药获得 $2$ 个金子：  By @[chenxi2009](/user/1020063)