淘气的射手

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

有一个 $n\times m$ 的方格场地，每个格子可能有一个目标（#），也可能为空（.）。

射手选择一个格子作为射击起点，并选择右下、左下、左上、右上四个方向之一。以右下方向为例，若起点为 $(x,y)$，则会击中所有满足 $i\ge x$、$j\ge y$ 且 $|i-x|+|j-y|\le k$ 的目标；另外三个方向同理。

求一次射击最多能击中多少个目标。

输入格式

第一行是测试组数 $t$。每组第一行包含 $n,m,k$，接下来 $n$ 行描述方格。

输出格式

每组输出一个整数，表示最多击中的目标数。

样例输入 1

4
3 3 1
.#.
###
.#.
2 5 3
###..
...##
4 4 2
..##
###.
#..#
####
2 1 3
#
#

样例输出 1

3
4
5
2

数据范围

$1\le t\le1000$，$1\le n,m,k\le10^5$，$n\cdot m\le10^5$，所有测试组的 $n\cdot m$ 之和不超过 $10^5$。