Background

Note: In the original problem (Java), the time limit is 3.0 s and the memory limit is 512 MB.

Problem Description

Tetris is a popular game worldwide. In the game there are many kinds of block patterns, and we only focus on these four classic block patterns: LITS, as shown in the figure below:

These four LITS blocks are each made up of four small squares of the same size.
Now you are given a grid of size $N \times N$. Each cell contains a number $0/1$. If a cell contains $1$, it means there is a small square in this cell; if it contains $0$, then there is none.
You need to determine whether it is possible to find the four LITS block patterns in this grid (each block pattern is independent, and there is no case where different patterns share the same small square). For the LITS blocks, rotating the shape by any number of $90^\circ$ turns is allowed, but flipping is not allowed.

Input Format

The first line contains an integer $T$, meaning there are $T$ test cases.
For each test case, the first line contains an integer $N$, representing the grid size.
Then follow $N$ lines, each containing $N$ integers with value $0/1$, representing the grid layout.

Output Format

For each test case, output one line containing a string. If this test case satisfies the requirement, output Yes; otherwise output No.

2
5
1 1 1 1 1
1 0 1 1 0
1 0 0 0 1
1 0 1 0 1
1 1 1 1 1
5
1 0 0 1 1
1 1 1 1 1
1 1 1 1 0
1 1 1 0 1
0 1 1 1 1

No
Yes

Hint

【Sample Explanation】

For the second grid in the samples, one possible placement of LITS is as follows:

1 0 0 1 1
L S T T T
L S S T 0
L L S 0 1
0 I I I I

【Constraints】

• For $30\%$ of the test cases: $1 \leq N \leq 5$.
• For $60\%$ of the test cases: $1 \leq N \leq 10$.
• For $100\%$ of the test cases: $1 \leq T \leq 10$, $1 \leq N \leq 50$.

【Special Note】

Because there are many cases to consider, some solutions on other platforms for this problem may be incorrect.

Translated by ChatGPT 5