CF1921G.Mischievous Shooter

Once the mischievous and wayward shooter named Shel found himself on a rectangular field of size $n \times m$, divided into unit squares. Each cell either contains a target or not.

Shel only had a lucky shotgun with him, with which he can shoot in one of the four directions: right-down, left-down, left-up, or right-up. When fired, the shotgun hits all targets in the chosen direction, the Manhattan distance to which does not exceed a fixed constant $k$. The Manhattan distance between two points $(x_1, y_1)$ and $(x_2, y_2)$ is equal to $|x_1 - x_2| + |y_1 - y_2|$.

Possible hit areas for $k = 3$.

Shel's goal is to hit as many targets as possible. Please help him find this value.

一位名叫谢尔（Shel）的顽皮而任性的射手，偶然间来到了一块尺寸为 $n \times m$ 的矩形场地，该场地被划分为若干单位方格。每个方格中要么有一个靶子，要么没有。

谢尔随身只带了一把“幸运散弹枪”，他可以用它朝四个方向之一射击：右下、左下、左上或右上。开枪时，散弹枪会击中所选方向上所有曼哈顿距离不超过固定常数 $k$ 的靶子。两点 $(x_1, y_1)$ 与 $(x_2, y_2)$ 之间的曼哈顿距离定义为 $|x_1 - x_2| + |y_1 - y_2|$。

当 $k = 3$ 时可能的命中区域。

谢尔的目标是尽可能多地击中靶子。请帮助他求出这个最大值。

Each test consists of several test cases. The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. Then follows the description of the test cases.

The first line of each test case contains field dimensions $n$, $m$, and the constant for the shotgun's power $k$ ($1 \le n, m, k \le 10^5, 1 \le n \cdot m \le 10^5$).

Each of the next $n$ lines contains $m$ characters — the description of the next field row, where the character '.' means the cell is empty, and the character '#' indicates the presence of a target.

It is guaranteed that the sum of $n \cdot m$ over all test cases does not exceed $10^5$.

每个测试包含若干测试用例。第一行包含一个整数 $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$。

For each test case, output a single integer on a separate line, which is equal to the maximum possible number of hit targets with one shot.

对于每个测试用例，在单独一行上输出一个整数，该整数等于一次射击所能击中的目标的最大可能数量。

Possible optimal shots for the examples in the statement:

语句中示例的可能最优射击方案：