← 返回题目列表

Codeforces · 1921/G

G. 恶作剧射手

中文机器翻译题面 查看原题

有一次,顽皮又任性的射手谢尔发现自己身处一个大小为 $$$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

注意

声明中示例的可能最佳镜头: