Black-and-White Blocks

Problem Description

Xiao Yang has a grid with $n$ rows and $m$ columns, where each cell is either white or black.

He wants to know whether there exists a sub-rectangle in the grid satisfying the following conditions:

• The sub-rectangle consists of $4$ rows and $4$ columns;
• The 1st and 4th rows of the sub-rectangle contain only white cells;
• For the 2nd and 3rd rows of the sub-rectangle, only the 1st and 4th cells are white, and all the other cells are black.

Write a program to help Xiao Yang decide.

Input Format

The first line contains a positive integer $t$, the number of test cases.

The following are $t$ test cases. Each test case consists of $n + 1$ lines.

The first line contains two positive integers $n, m$, as described.

The following $n$ lines each contain a string of length $m$ consisting of 0 and 1, representing the colors of the cells in the $i$-th row of the grid. If a character is 0, the corresponding cell is white; otherwise it is black.

Output Format

For each test case, if such a sub-rectangle exists, output Yes; otherwise output No.

Sample Input

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

Sample Output

No
Yes
No

Sample Explanation

For the first test case, the grid is $1 \times 4$, so no $4 \times 4$ sub-rectangle can be chosen; therefore no qualified sub-rectangle exists, and the output is No. The second test case has a qualified sub-rectangle, so the output is Yes. The third test case has no such sub-rectangle, so the output is No.

Constraints

For all test data, $1 \le t \le 10$ and $1 \le n, m \le 100$ are guaranteed.