Victorino Mapa 热爱物理地图。他最喜欢的部分是将地图折叠成一个小正方形，然后在重新展开时观察折痕形成的图案。他非常喜欢这个过程，以至于他为折叠地图创造了一种很酷的新符号。

他以某种顺序执行一系列折叠：一些沿水平轴，一些沿垂直轴。每次水平折叠都在距离纸张顶部整数个单位的位置进行，折痕总是横跨纸张的整个宽度（垂直折叠同理）。Victorino 只有在纸张被折叠成单位正方形时才会停止。

以下是对 $3 \times 4$ 地图进行此类折叠的示例。

当 Victorino 再次展开这张纸时，他会得到一张看起来像这样的地图：

折痕线创造了一个 $m \times n$ 的单位正方形网格！Victorino 将此过程称为“流形法”（manifold method），而流形法的结果就是“流形地图”（manifolded map）。

令折叠指代由两个相邻单元格共享的边（长度为 1 个单位）。根据折痕的方向，每次折叠可以分为两种类型。假设你正对着地图表面——向你凸起的折痕是山折（mountain folds），向远离你方向凹陷的折痕是谷折（valley folds）。

在下图中，我们将上述示例中的纸张展平。山折用实线标记，谷折用虚线标记。

Victorino 设计了以下方案，将流形地图编码为 ASCII 字符网格。在他向你描述之前，让我们看一个具体的例子——他编码了刚才的流形地图。

.V.V.M.
M+M+M+M
.M.M.V.
V+M+V+M
.M.M.V.

形式上，令 $s$ 为一个 $(2r - 1) \times (2c - 1)$ 的网格，其中 $s_{i,j}$ 是从顶部起第 $i$ 行、从左侧起第 $j$ 列的字符。

• 如果 $i$ 和 $j$ 均为奇数，则 $s_{i,j}$ 为 .，表示网格中的一个单位正方形。
• 如果 $i$ 和 $j$ 均为偶数，则 $s_{i,j}$ 为 +，表示四个正方形相交的角。
• 否则，$s_{i,j}$ 表示被该字符相邻的两个单位正方形所包围的折叠；如果是山折，则为 M；如果是谷折，则为 V。

Victorino 意识到这个乐趣也可以反过来。给定一个 ASCII 网格，挑战在于在执行流形法时做出正确的选择，以复制网格所描述的图案——也就是说，如果这在现实中是可能的话。

给定这样一个网格，请确定（仅输出 YES 或 NO）是否可以在现实中复制出一个流形地图，使其在使用 Victorino 的编码方案表示时产生该图案。此外，每个文件包含 $T$ 个独立的测试用例。

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。接下来是 $T$ 个测试用例的描述。

每个测试用例的第一行包含两个空格分隔的整数 $r$ 和 $c$。

随后是 $2r - 1$ 行，每行包含一个长度为 $2c - 1$ 的字符串。

这就是我们希望使用流形法复制其图案的 $(2r - 1) \times (2c - 1)$ 网格。

输出格式

对于每个测试用例，输出一行，包含字符串 YES 或 NO。

数据范围

• $1 \le T \le 80$
• $1 \le r, c \le 50$
• $2 \le rc$
• 输入遵循 Victorino 的编码方案格式。

样例

样例输入 1

2
3 4
.V.V.M.
M+M+M+M
.M.M.V.
V+M+V+M
.M.M.V.
2 2
.M.
M+M
.M.

样例输出 1

YES
NO