A16370. 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.

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$ .

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: