G. Озорной стрелок
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Однажды непутёвый озорной стрелок по имени Шел попал на прямоугольное поле размером $$$n \times m$$$, разбитое на единичные квадратики. В каждой из клеток либо стоит мишень, либо нет.

С собой у Шел оказался только счастливый дробовик, из которого можно выстрелить в одну из четырёх сторон: вправо-вниз, влево-вниз, влево-вверх или вправо-вверх. При выстреле дробовик поражает все мишени в выбранном направлении, Манхэттенское расстояние до которых не больше фиксированной для дробовика константы $$$k$$$. Манхэттенское расстояние между двумя точками $$$(x_1, y_1)$$$ и $$$(x_2, y_2)$$$ равно $$$|x_1 - x_2| + |y_1 - y_2|$$$.

Возможные области поражения для $$$k = 3$$$.

Цель Шел — поразить как можно большее количество мишеней. Помогите ему, пожалуйста, найти это значение.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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$$$.

Выходные данные

Для каждого набора входных данных в отдельной строке выведите одно число, которое равно максимально возможному количеству поражённых мишеней за один выстрел.

Пример
Входные данные
4
3 3 1
.#.
###
.#.
2 5 3
###..
...##
4 4 2
..##
###.
#..#
####
2 1 3
#
#
Выходные данные
3
4
5
2
Примечание

Возможные оптимальные выстрелы для примеров из условия: