题目描述

给定一个 $n$ 行 $m$ 列的网格。

我们用 $(i, j)$ 表示网格中从上到下第 $i$ 行从左往右第 $j$ 列的那个格子。所以网格左上角的格子为 $(1, 1)$，右下角的格子为 $(n, m)$。

初始时，网格中的所有格子都没有被染色。

然后你可以使用 对称之勾染色法 对这个网格进行染色。

一个大小为 $d(d \gt 0)$ 的对称之勾定义如下：

首先，对称之勾有一个中心点 $(i, j)$；其次，以中心点 $(i, j)$ 为起点，连续往左上方移动 $d$ 格所经过的所有点（即：$(i-1, j-1), (i-2, j-2), \ldots, (i-d,j-d)$）以及连续往右上方移动 $d$ 格所经过的所有点（即：$(i-1, j+1), (i-2, j+2), \ldots, (i-d, j+d)$）$\Rightarrow$ 如果这 $2d+1$ 个点都是实际存在于网格内的点（没有越出网格边界外），则我们称这是一个以 $(i, j)$ 为中心点，大小为 $d$ 的 对称之勾。

概括地说，如果 $1 \le i-d \le i \le n$ 且 $1 \le j-d \le j+d \le m$，则我们称由集合 $\{\ (i-h, j \pm h)\ |\ 0 \le h \le d\ \}$ 中的所有点构成的图形为一个大小为 $d$ 的对称之勾。

比如，下图演示了一个 $4 \times 9$ 的网格，对其进行两次对称之勾染色，分别对以 $(3,3)$ 为中心点的大小为 $2$ 的对称之勾，和以 $(4, 6)$ 为中心点的大小为 $3$ 的对称之勾上的所有格子染色之后的最终效果图（其中蓝色表示染色的格子，白色是未染色的格子）：

你可以使用任意次对称之勾染色法对这个网格进行染色，你每次可以选择一个大小至少为 $k$ 的对称之勾（即每次选择染色的对称之勾的大小 $d$ 必须满足 $d \ge k$），然后将所有在该对称之勾上的格子染色。

每一个格子可以重复被染色。

现在告诉你这个网格的最终效果图，请你判断能否通过若干次对称之勾染色法将一个初始每个格子都没有染色的网格染成这个最终效果图？

输入格式

输入包含多组测试数据。

输入的第一行包含一个整数 $t(1 \le t \le 100)$。

接下来为每组测试数据的描述。

第一行包含三个整数 $n, m, k(1 \le k \le n \le 100; 1 \le m \le 200)$，分别表示网格的行数，列数，以及可以使用的对称之勾的大小的最小值。

接下来 $n$ 行，每行包含一个长度为 $m$ 的字符串，表示网格的最终效果图。其中 * 号表示格子被染色，. 号表示格子没有被染色。

输出格式

对于每组测试数据，输出一行。如果这个这个网格的最终效果图可以使用若干个大小至少为 $k$ 的对称之勾染色，输出 "YES"；否则，输出 "NO"。

input

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

output

NO
YES
YES
YES
NO
NO
NO
NO

说明/提示

样例解释

第2组测试数据：以 $(3,3)$ 为中心点大小为 $2$ 的对称之勾 + 以 $(4,6)$ 为中心大小为 $3$ 的对称之勾

第3组测试数据：以 $(2,2)$ 为中心大小为 $1$ 的对阵之勾 + 以 $(3,2)$ 为中心大小为 $1$ 的对阵之勾 + 以 $(3,3)$ 为中心大小为 $1$ 的对阵之勾

第4组测试数据：以 $(4,3)$ 为中心大小为 $2$ 的对阵之勾 + 以 $(5,4)$ 为中心大小为 $1$ 的对阵之勾

数据规模与约定

• 对于 $50\%$ 的数据，$t \le 10; n \le 10; m \le 20$
• 对于 $100\%$ 的数据，$1 \le t \le 100; 1 \le k \le n \le 100; m \le 200$