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

У Казимира есть прямоугольный лист бумаги с клетчатым полем размера $$$n \times m$$$. Изначально все клетки поля пустые.

Обозначим клетку с координатами $$$i$$$ по вертикали и $$$j$$$ по горизонтали за $$$(i, j)$$$. Тогда левая верхняя клетка будет обозначаться как $$$(1, 1)$$$, а правая нижняя — как $$$(n, m)$$$.

Казимир рисует на поле галочки разных размеров. Галочка размера $$$d$$$ ($$$d > 0$$$) с вершиной в клетке $$$(i, j)$$$ рисуется следующим образом:

  1. Сначала закрашивается клетка $$$(i, j)$$$.
  2. Затем закрашиваются $$$d$$$ клеток слева-сверху по диагонали от вершины и $$$d$$$ клеток справа-сверху по диагонали от вершины.
  3. Итого закрашенными оказываются клетки с координатами $$$(i - h, j \pm h)$$$ для всех $$$h$$$ от $$$0$$$ до $$$d$$$. В частности, галочка состоит из $$$2d + 1$$$ закрашенных клеток.

Если повторно закрасить уже закрашенную клетку, она останется закрашенной. Снизу приведен пример поля $$$4 \times 9$$$, на котором нарисованы две галочки размеров $$$2$$$ и $$$3$$$.

Вам дано описание клетчатого поля размера $$$n \times m$$$. Казимир утверждает, что это поле получилось после того, как он нарисовал на нем сколько-то (возможно, $$$0$$$) галочек. Галочки могли быть разного размера, но размер каждой из них не меньше $$$k$$$ (то есть $$$d \ge k$$$ для всех галочек).

Проверьте, можно ли получить заданную картинку, нарисовав несколько (возможно, ноль) галочек, для каждой из которых $$$d \ge k$$$.

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

В первой строке записано целое число $$$t$$$ ($$$1 \leq t \leq 100$$$) — количество наборов входных данных.

В следующих строках по очереди даны описания наборов входных данных.

В описании каждого набора входных данных первая строка содержит целые числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \le k \le n \le 10$$$; $$$1 \le m \le 19$$$) — размеры поля и минимальный размер галочек, которые рисовал Казимир. В следующих $$$n$$$ строках описания дано описание поля: каждая строка состоит из $$$m$$$ символов, каждый из которых равен '.', если эта клетка пустая, и '*', если закрашенная.

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

Выведите $$$t$$$ строк, каждая из которых содержит ответ на соответствующий набор входных данных. В качестве ответа выведите YES, если данное поле могло быть получено из пустого рисованием галочек размеров $$$\ge k$$$, и NO в противном случае.

Вы можете выводить ответ в любом регистре (например, строки yEs, yes, Yes и YES будут распознаны как положительный ответ).

Пример
Входные данные
8
2 3 1
*.*
...
4 9 2
*.*.*...*
.*.*...*.
..*.*.*..
.....*...
4 4 1
*.*.
****
.**.
....
5 5 1
.....
*...*
.*.*.
..*.*
...*.
5 5 2
.....
*...*
.*.*.
..*.*
...*.
4 7 1
*.....*
.....*.
..*.*..
...*...
3 3 1
***
***
***
3 5 1
*...*
.***.
.**..
Выходные данные
NO
YES
YES
YES
NO
NO
NO
NO
Примечание

Первый набор данных из примера состоит из двух звездочек, которые не могут являться самостоятельными галочками, так как не существует галочек размера $$$0$$$.

Второй набор данных из примера описан в условии (см. рисунок в тексте условия). Такое поле может быть получено, если нарисовать галочки размеров $$$2$$$ и $$$3$$$, как и показано на рисунке.

Поле в третьем наборе данных соответствует трем нарисованным галочкам размера $$$1$$$. Их вершины ниже обозначены $$$\color{blue}{\text{синим}}$$$, $$$\color{red}{\text{красным}}$$$ и $$$\color{green}{\text{зеленым}}$$$ цветами:

*.*.
*$$$\color{blue}{\textbf{*}}$$$**
.$$$\color{green}{\textbf{*}}\color{red}{\textbf{*}}$$$.
....

Поле в четвертом наборе данных из примера могло быть получено рисованием двух галочек размеров $$$1$$$ и $$$2$$$. Их вершины отмечены ниже $$$\color{blue}{\text{синим}}$$$ и $$$\color{red}{\text{красным}}$$$ цветами соответственно:

.....
*...*
.*.*.
..$$$\color{red}{\textbf{*}}$$$.*
...$$$\color{blue}{\textbf{*}}$$$.

Поле в пятом наборе данных из примера не может быть получено, так как $$$k = 2$$$, а последняя звездочка в четвертой сверху строке с координатами $$$(4, 5)$$$ может быть только частью галочки размера $$$1$$$.

Поле в шестом наборе данных из примера не может быть получено, так как левая верхняя звездочка $$$(1, 1)$$$ не может быть самостоятельной галочкой, так как размеры галочек должны быть положительными, и не может быть частью галочки с вершиной в нижнем ряду, так как отделена от нее разрывом (точкой, '.') в $$$(2, 2)$$$.

В седьмом наборе данных, аналогично, поле не может быть получено, так как звездочки с координатами $$$(1, 2)$$$ (центральная верхняя), $$$(3, 1)$$$ и $$$(3, 3)$$$ (крайние нижние) не могут быть частью никаких галочек.