背景

GESP四级真题(202409)

描述

⼩杨有⼀个 $n$ ⾏ $m$ 列的⽹格图，其中每个格⼦要么是⽩⾊，要么是⿊⾊。

⼩杨想知道⽹格图中是否存在⼀个满⾜如下条件的⼦矩形：

• ⼦矩形由 4 ⾏ 4 列组成；
• ⼦矩形的第 1 ⾏ 和第 4 ⾏只包含⽩⾊格⼦；
• 对于⼦矩形的第 2 ⾏ 和第 3 ⾏，只有第 1 个和第 4 个格⼦是⽩⾊的，其余格⼦都是⿊⾊的；
• 请你编写程序帮助⼩杨判断。

格式

输入

第⼀⾏包含⼀个正整数 $t$，代表测试⽤例组数。

接下来是 $t$ 组测试⽤例。对于每组测试⽤例，⼀共 $n+1$ ⾏。

第⼀⾏包含两个正整数 $n,m$ ，含义如题⾯所⽰。

之后 $n$ ⾏，每⾏⼀个长度为 $m$ 的 01 串，代表⽹格图第 $i$ ⾏格⼦的颜⾊，如果为 0 ，则对应格⼦为⽩⾊，否则为⿊⾊。

输出

对于每组测试⽤例，如果存在，输出 Yes，否则输出 No。

样例

3
1 4
0110
5 5
00000
01100
01100
00001
01100
5 5
00000
01100
01110
00001
01100

No
Yes
No

样例解释

满⾜条件的⼦矩形形如：

0000
0110
0110
0000

数据规模

对于全部数据，保证有 。$1 \le t \le 10, 1 \le n, m \le 100$。

限制

时间限制：1.0 s

空间限制：512.0 MB