题目内容

在一项安全检测系统中，需要分析一个 $n$ 行 $m$ 列的二进制网格。网格的每个位置要么是 1（表示检测点），要么是 0（表示空位）。一个网格被认为是有效的，当且仅当同时满足以下两个条件：

• 行数 $n$ 和列数 $m$ 均为偶数；
• 在网格中存在一个 $2 \times 2$ 的连续子网格，其中四个位置全部为 1。

现在给出 $T$ 个待检测的网格，请你依次判断每一个网格是否有效。

数据范围：

• 测试数据组数 $T$ 满足 $1 \le T < 10$。
• 行数 $n$ 和列数 $m$ 满足 $1 \le n, m \le 500$。
• 网格中仅包含字符 0 和 1。

输入描述

每个测试文件包含多组测试数据。第一行输入一个整数 $T$ $(1 \le T < 10)$，代表数据组数。每组测试数据描述如下： 第一行输入两个整数 $n$ 和 $m$ $(1 \le n, m \le 500)$，代表网格的行数和列数。 接下来 $n$ 行，每行输入一个长度为 $m$ 且仅包含字符 0 和 1 的字符串，表示该行网格的具体情况。

输出描述

对于每一组测试数据，如果该网格有效，在一行上输出 YES；否则，输出 NO。

样例1

输入

1
4 4
1110
1110
0000
0000

输出

YES

说明

网格行数 $n = 4$ 和列数 $m = 4$ 均为偶数，满足第一个条件。检查所有 $2 \times 2$ 子网格，发现左上角（第 1~2 行，第 1~2 列）的四个元素 1、1、1、1 全部为 1，存在所需的 $2 \times 2$ 全 1 正方形。

两个条件同时满足，因此该网格有效，输出 YES。

样例2

输入

1
2 2
00
00

输出

NO

说明

网格行数 $n = 2$ 与列数 $m = 2$ 均为偶数，满足第一个条件。但遍历唯一的 $2 \times 2$ 子网格（即整个网格）发现四个元素全部为 0，不满足“四个位置全部为 1”的要求，因此不存在所需的 $2 \times 2$ 全 1 正方形。

网格无效，输出 NO。

样例3

输入

1
3 2
11
11
00

输出

NO

说明

网格行数 $n = 3$ 是奇数，不满足“行数和列数均为偶数”这一前提条件。即便左上角的 $2 \times 2$ 子网格四个位置全部为 1，由于第一个条件已经失败，网格直接判定为无效。

输出 NO。

样例4

输入

1
2 2
11
11

输出

YES

说明

这是最小的有效边界情况：行数 $n = 2$、列数 $m = 2$ 均为偶数，且整个网格本身就是一个全为 1 的 $2 \times 2$ 正方形，同时满足两个条件。

因此网格有效，输出 YES。