题目内容

小明在矩形庭院中用固定大小的方形草皮进行装饰，每块草皮恰好覆盖一个 $2 \times 2$ 的区域。为了留出足够的过道，草皮之间必须严格隔开：任意两块不同的草皮不允许共享边或共享角（即它们在八个方向上都不能相邻）。铺好后，小明用字符 * 表示有草皮的格子，. 表示空地，得到了一个 $n$ 行 $m$ 列的图案。

现在小明想知道，给定一个图案，是否能恰好由若干块符合上述不相邻要求的 $2 \times 2$ 草皮铺设而成。具体来说，图案必须满足：

• 每个 * 必须属于某个完整的 $2 \times 2$ 草皮块，且每个 * 只能属于一个草皮块；
• 任意两个 $2 \times 2$ 草皮块之间不能存在任何相邻的格子（包括水平、垂直以及对角方向）。

如果图案中存在残缺的 $2 \times 2$ 部分，或者有孤立的 * 无法构成完整的草皮块，或者草皮块之间发生了相邻，则该图案是不合法的。

约束条件：共有 $t$ 组询问，所有询问中行数 $n$、列数 $m$ 以及询问数 $t$ 均不超过 50。

输入描述

第一行包含一个正整数 t，表示询问的次数。 对于每组询问： 第一行包含两个正整数 n 和 m，分别表示矩阵的行数和列数。 接下来的 n 行，每行包含一个长度为 m 的字符串，字符串仅由字符 * 和 . 组成，* 表示该位置铺有草皮，. 表示该位置为空地。

输出描述

共输出 t 行，每行输出一个字符串 Yes 或 No，分别表示对应图案是否可以由符合要求的不相邻 $2 \times 2$ 草皮铺设而成。

样例1

输入

1
2 2
**
**

输出

Yes

说明

图案由一个完整的 $2 \times 2$ 草皮块组成，四周没有其他 *，完全符合要求。

样例2

输入

1
5 5
**...
**...
.....
...**
...**

输出

Yes

说明

图案包含两个 $2 \times 2$ 草皮块，分别位于左上角 (0,0)-(1,1) 和右下角 (3,3)-(4,4)。两个草皮块之间在水平、垂直和对角方向上均没有相邻的格子，因此合法。

样例3

输入

1
4 4
**..
**..
....
...*

输出

No

说明

左上角有一个完整的 $2 \times 2$ 草皮块，但右下角存在一个孤立的 *。该孤立的 * 无法与任何其他格子构成完整的 $2 \times 2$ 草皮，因此图案不合法。

样例4

输入

1
2 3
***
***

输出

No

说明

整个图案是一个 $2 \times 3$ 的矩形，全由 * 组成。任何试图在其中选取一个 $2 \times 2$ 草皮块，都会使得剩余的 * 与已选草皮块相邻（水平方向），违反了草皮之间必须严格不相邻的规则。同时，多余的 * 也无法凑成另一个完整的 $2 \times 2$ 块，因此不合法。