题目描述

Y2hlOTYw 是一名国际象棋爱好者。然而，他没有自己的棋盘。

一天，他得到了一张 $n$ 行 $m$ 列的黑白双色网格纸。这当然不会是一个标准的国际象棋棋盘，不过 Y2hlOTYw 可管不了这么多。他认为，如果所有同色格子通过上下左右相邻形成的每个连通块，其形状都必须是矩形，这张网格纸就能当成棋盘用。

现在 Y2hlOTYw 想让你帮忙判断一下，这张网格纸能不能当成棋盘用。

形式化地，设网格纸为 $G = \{(i, j) \mid 1 \le i \le n,\ 1 \le j \le m\}$，其中 $n$ 和 $m$ 为正整数。每个格子 $(i,j)$ 被赋予一种颜色 $\text{color}(i,j) \in \{\text{black},\text{white}\}$。

两个格子 $(i,j)$ 与 $(i',j')$ 相邻当且仅当 $|i-i'| + |j-j'| = 1$。

对于固定的颜色 $c \in \{\text{black},\text{white}\}$，考虑子集 $S_c = \{(i,j)\in G \mid \text{color}(i,j) = c\}$。在 $S_c$ 上定义等价关系：两个格子等价当且仅当存在格子序列 $(i_1,j_1), (i_2,j_2), \dots, (i_k,j_k)$ 使得每个格子都属于 $S_c$，且对于任意的 $t$（$1\le t\le k-1$）都有格子 $(i_t,j_t)$ 与格子 $(i_{t+1},j_{t+1})$ 相邻。每个等价类称为一个连通块。一个连通块是极大的，即不能通过添加任何相邻的同色格子而扩大。

一个格子集合 $R \subseteq G$ 的形状被称为矩形，如果存在整数 $r_1 \le r_2$ 和 $c_1 \le c_2$ 使得：

$$R = \{(i,j) \mid r_1 \le i \le r_2,\ c_1 \le j \le c_2\}$$

现在需要判断：每一个连通块的形状，是否都是矩形。

输入格式

本题包含多组测试用例。输入的第一行，包含一个正整数 $T$（$1\le T\le 8266$），表示测试用例的数量。

接下来是 $T$ 组测试用例的描述。

每个测试用例的第一行，包含两个整数 $n$ 和 $m$ ($1 \le n,m \le 500$)，用一个空格分隔，表示网格纸有 $n$ 行 $m$ 列。

接下来 $n$ 行，第 $i$ 行包含一个长度恰为 $m$ 的字符串 $S_i$，表示给定的网格纸。保证字符串 $S_i$ 仅包含字符 $\texttt{0}$ 和 $\texttt{1}$。其中，对于任意的整数 $i$ 和 $j$（$1\le i\le n, 1 \le j \le m$）：

• 若第 $i$ 行第 $j$ 个字符为 $\texttt{1}$，表示网格纸第 $i$ 行第 $j$ 列的格子 $(i,j)$ 的颜色为黑色（$\text{black}$）；
• 若第 $i$ 行第 $j$ 个字符为 $\texttt{0}$，表示网格纸第 $i$ 行第 $j$ 列的格子 $(i,j)$ 的颜色为白色（$\text{white}$）。

保证所有测试用例中 $n\cdot m$ 的总和不超过 $2.5 \times 10^5$。

输出格式

对于每个测试用例，输出一行，包含一个字符串：

• 若这张网格纸能当成棋盘用，即每一个连通块的形状都是矩形，则输出 $\tt{Yes}$；
• 否则，输出 $\tt{No}$。

答案对大小写不敏感。例如 $\tt{yEs}$，$\tt{Yes}$，$\tt{yes}$ 和 $\tt{YES}$ 都会被视为 $\tt{Yes}$。

4
2 3
110
110
4 3
110
111
111
111
5 5
00000
01110
01010
01110
00000
8 8
01010101
10101010
01010101
10101010
01010101
10101010
01010101
10101010

Yes
No
No
Yes