有一次,顽皮又任性的射手谢尔发现自己身处一个大小为 $$$n \times m$$$ 的矩形场地,分为多个单位方块。每个单元格要么包含目标,要么不包含目标。
谢尔身上只有一把幸运霰弹枪,他可以用它向四个方向之一射击:右下、左下、左上或右上。发射时,霰弹枪击中所选方向上的所有目标,曼哈顿距离不超过固定常数$$$k$$$。两点 $$$(x_1, y_1)$$$ 和 $$$(x_2, y_2)$$$ 之间的曼哈顿距离等于 $$$|x_1 - x_2| + |y_1 - y_2|$$$。
$$$k = 3$$$ 的可能命中区域。
Shel 的目标是击中尽可能多的目标。请帮他找到这个值。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) - 测试用例的数量。然后是测试用例的描述。
每个测试用例的第一行包含字段尺寸 $$$n$$$、$$$m$$$ 和霰弹枪威力常数 $$$k$$$ ($$$1 \le n, m, k \le 10^5, 1 \le n \cdot m \le 10^5$$$)。
接下来的 $$$n$$$ 行包含 $$$m$$$ 个字符 — 下一个字段行的描述,其中字符“.”表示单元格为空,字符“#”表示存在目标。
保证所有测试用例的 $$$n \cdot m$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,在单独的行上输出一个整数,该整数等于一次射击击中目标的最大可能数量。
示例
输入 #1
4 3 3 1 .#. ### .#. 2 5 3 ###.. ...## 4 4 2 ..## ###. #..# #### 2 1 3 # #
输出 #1
3 4 5 2
注意
声明中示例的可能最佳镜头: