CF1579C.Ticks

Casimir has a rectangular piece of paper with a checkered field of size $n \times m$. Initially, all cells of the field are white.

Let us denote the cell with coordinates $i$ vertically and $j$ horizontally by $(i, j)$. The upper left cell will be referred to as $(1, 1)$ and the lower right cell as $(n, m)$.

Casimir draws ticks of different sizes on the field. A tick of size $d$ ($d \gt 0$) with its center in cell $(i, j)$ is drawn as follows:

1. First, the center cell $(i, j)$ is painted black.
2. Then exactly $d$ cells on the top-left diagonally to the center and exactly $d$ cells on the top-right diagonally to the center are also painted black.
3. That is all the cells with coordinates $(i - h, j \pm h)$ for all $h$ between $0$ and $d$ are painted. In particular, a tick consists of $2d + 1$ black cells.

An already painted cell will remain black if painted again. Below you can find an example of the $4 \times 9$ box, with two ticks of sizes $2$ and $3$.

You are given a description of a checkered field of size $n \times m$. Casimir claims that this field came about after he drew some (possibly $0$) ticks on it. The ticks could be of different sizes, but the size of each tick is at least $k$ (that is, $d \ge k$ for all the ticks).

Determine whether this field can indeed be obtained by drawing some (possibly none) ticks of sizes $d \ge k$ or not.

卡西米尔有一张 $n \times m$ 的方格纸。初始时，方格中所有单元格均为白色。

我们用 $(i, j)$ 表示第 $i$ 行（从上往下数）、第 $j$ 列（从左往右数）的单元格。左上角单元格记为 $(1, 1)$，右下角单元格记为 $(n, m)$。

卡西米尔在方格纸上绘制不同尺寸的“勾号”（tick）。一个尺寸为 $d$（$d > 0$）且中心位于单元格 $(i, j)$ 的勾号按如下方式绘制：

1. 首先，将中心单元格 $(i, j)$ 涂黑；
2. 然后，恰好将中心单元格左上方对角线方向的 $d$ 个单元格、以及右上方对角线方向的 $d$ 个单元格也涂黑；
3. 即：对所有满足 $0 \le h \le d$ 的整数 $h$，将坐标为 $(i - h, j \pm h)$ 的所有单元格涂黑。特别地，一个尺寸为 $d$ 的勾号共包含 $2d + 1$ 个黑色单元格。

若某个单元格已被涂黑，则再次涂黑不会改变其颜色（即黑色保持不变）。下方是一个 $4 \times 9$ 的方格示例，其中绘制了两个尺寸分别为 $2$ 和 $3$ 的勾号。

现给你一个 $n \times m$ 方格的描述（即每个单元格是黑还是白）。卡西米尔声称该方格是在他绘制了若干（可能为 $0$ 个）勾号之后得到的。这些勾号可以具有不同尺寸，但每个勾号的尺寸至少为 $k$（即所有勾号均满足 $d \ge k$）。

请判断：该方格是否确实可能通过绘制若干（可为零个）尺寸均不小于 $k$ 的勾号而得到。

The first line contains an integer $t$ ($1 \leq t \leq 100$) — the number test cases.

The following lines contain the descriptions of the test cases.

The first line of the test case description contains the integers $n$, $m$, and $k$ ($1 \le k \le n \le 10$; $1 \le m \le 19$) — the field size and the minimum size of the ticks that Casimir drew. The following $n$ lines describe the field: each line consists of $m$ characters either being '.' if the corresponding cell is not yet painted or '*' otherwise.

第一行包含一个整数 $t$（$1 \leq t \leq 100$）—— 表示测试用例的数量。

接下来的若干行包含各测试用例的描述。

每个测试用例的第一行包含三个整数 $n$、$m$ 和 $k$（$1 \leq k \leq n \leq 10$；$1 \leq m \leq 19$）—— 分别表示方格区域的尺寸以及卡西米尔所画刻度的最小尺寸。接下来的 $n$ 行描述该方格区域：每行由 $m$ 个字符组成，其中 '.' 表示对应单元格尚未被涂色，'*' 表示已被涂色。

Print $t$ lines, each line containing the answer to the corresponding test case. The answer to a test case should be YES if the given field can be obtained by drawing ticks of at least the given size and NO otherwise.

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes, and YES will all be recognized as positive answers).

输出 $t$ 行，每行包含对应测试用例的答案。若给定的方格图可通过绘制至少指定大小的“tick”（勾号）得到，则答案为 YES；否则为 NO。

您可以以任意大小写形式输出每个字母（例如，字符串 yEs、yes、Yes 和 YES 均被视为肯定回答）。

The first sample test case consists of two asterisks neither of which can be independent ticks since ticks of size $0$ don't exist.

The second sample test case is already described in the statement (check the picture in the statement). This field can be obtained by drawing ticks of sizes $2$ and $3$, as shown in the figure.

The field in the third sample test case corresponds to three ticks of size $1$. Their center cells are marked with $\color{blue}{\text{blue}}$, $\color{red}{\text{red}}$ and $\color{green}{\text{green}}$ colors:

*.*.

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

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

....

The field in the fourth sample test case could have been obtained by drawing two ticks of sizes $1$ and $2$. Their vertices are marked below with $\color{blue}{\text{blue}}$ and $\color{red}{\text{red}}$ colors respectively:

.....

*...*

.*.*.

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

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

The field in the fifth sample test case can not be obtained because $k = 2$, and the last asterisk in the fourth row from the top with coordinates $(4, 5)$ can only be a part of a tick of size $1$.

The field in the sixth sample test case can not be obtained because the top left asterisk $(1, 1)$ can't be an independent tick, since the sizes of the ticks must be positive, and cannot be part of a tick with the center cell in the last row, since it is separated from it by a gap (a point, '.') in $(2, 2)$.

In the seventh sample test case, similarly, the field can not be obtained by the described process because the asterisks with coordinates $(1, 2)$ (second cell in the first row), $(3, 1)$ and $(3, 3)$ (leftmost and rightmost cells in the bottom) can not be parts of any ticks.

第一个样例测试用例包含两个星号（*），但它们均不能作为独立的“刻度”（tick），因为尺寸为 $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)$（最底行最左与最右的格子）的星号无法成为任何刻度的一部分。