原题链接：

Problem - 1647B - Codeforces

题目描述：

Madoka's father just reached 11 million subscribers on Mathub! So the website decided to send him a personalized award — The Mathhub's Bit Button!

The Bit Button is a rectangular table with nn rows and mm columns with 00 or 11 in each cell. After exploring the table Madoka found out that:

• A subrectangle AA is contained in a subrectangle BB if there's no cell contained in AA but not contained in BB.
• Two subrectangles intersect if there is a cell contained in both of them.
• A subrectangle is called black if there's no cell with value 00 inside it.
• A subrectangle is called nice if it's black and it's not contained in another black subrectangle.
• The table is called elegant if there are no two nice intersecting subrectangles.

For example, in the first illustration the red subrectangle is nice, but in the second one it's not, because it's contained in the purple subrectangle.

Input:

Each test contains multiple test cases. The first line contains a single integer tt (1≤t≤2001≤t≤200) — the number of test cases. Description of the test cases follows.

The first line of each test case contains two positive integers n,mn,m (1≤n,m≤1001≤n,m≤100).

The next nn lines contain strings of length mm consisting of zeros and ones — the description of the table.

It is guaranteed that the sum of the values of nn and the sum of the values of mm for all test cases do not exceed 777777.

 

Output

For each test case print "YES" if its table is elegant or print "NO" otherwise.

You may print each letter in any case (for example, "YES", "Yes", "yes", "yEs" will all be recognized as positive answer).

Example

input

5
3 3
100
011
011
3 3
110
111
110
1 5
01111
4 5
11111
01010
01000
01000
3 2
11
00
11

output

YES
NO
YES
NO
YES

题目大意：

检查该矩阵的所有全1子矩阵是不是不重叠的。

解题思路：

结论很简单：所有2*2的子矩阵中1的个数不能为3。

代码（CPP）：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e2 + 10;
const int INF = 0x3fffffff;
int n, m, a[maxn][maxn];

/*
    结论很简单：所有2*2的子矩阵中1的个数不能为3
*/

int main()
{
    // freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;
    cout.precision(18);

    int t;
    cin >> t;
    while (t--)
    {
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
        {
            string s;
            cin >> s;
            s = " " + s;
            for (int j = 1; j <= m; j++)
            {
                a[i][j] = s[j] - '0';
            }
        }
        bool flag = true;
        for (int i = 1; i <= n - 1; i++)
        {
            for (int j = 1; j <= m - 1; j++)
            {
                int cnt = 0;
                for (int k = 0; k < 2; k++)
                {
                    for (int l = 0; l < 2; l++)
                    {
                        if(a[i + k][j + l] == 1)
                            cnt++;
                    }
                }
                if(cnt == 3)
                {
                    flag = false;
                    break;
                }
            }
            if(!flag)
                break;
        }
        cout << (flag ? "YES\n" : "NO\n");
    }
    return 0;
}