CF1360E.Polygon

Polygon is not only the best platform for developing problems but also a square matrix with side $n$, initially filled with the character 0.

On the polygon, military training was held. The soldiers placed a cannon above each cell in the first row and a cannon to the left of each cell in the first column. Thus, exactly $2n$ cannons were placed.

Initial polygon for $n=4$.

Cannons shoot character 1. At any moment of time, no more than one cannon is shooting. When a 1 flies out of a cannon, it flies forward (in the direction of the shot) until it collides with a polygon border or another 1. After that, it takes the cell in which it was before the collision and remains there. Take a look at the examples for better understanding.

More formally:

• if a cannon stands in the row $i$, to the left of the first column, and shoots with a 1, then the 1 starts its flight from the cell ($i, 1$) and ends in some cell ($i, j$);
• if a cannon stands in the column $j$, above the first row, and shoots with a 1, then the 1 starts its flight from the cell ($1, j$) and ends in some cell ($i, j$).

For example, consider the following sequence of shots:

1. Shoot the cannon in the row $2$. 2. Shoot the cannon in the row $2$. 3. Shoot the cannon in column $3$.

You have a report from the military training on your desk. This report is a square matrix with side length $n$ consisting of 0 and 1. You wonder if the training actually happened. In other words, is there a sequence of shots such that, after the training, you get the given matrix?

Each cannon can make an arbitrary number of shots. Before the training, each cell of the polygon contains 0.

多边形不仅是最优秀的题目开发平台，还是一块边长为 $n$ 的方阵，初始时所有格子均填有字符 0。

在该多边形上举行了军事训练。士兵们在第一行的每个格子上方各放置一门火炮，在第一列的每个格子左侧也各放置一门火炮。因此，总共放置了恰好 $2n$ 门火炮。

$n=4$ 时的初始多边形。

火炮发射字符 1。在任意时刻，至多只有一门火炮正在发射。当一个 1 从火炮中射出后，它将沿射击方向（即前进方向）飞行，直至撞到多边形边界或另一个 1；随后，它停留在碰撞发生前所在的那个格子中并保持不动。请参看示例以加深理解。

更形式化地描述如下：

• 若一门火炮位于第 $i$ 行、第一列左侧，并向右发射一个 1，则该 1 从格子 $(i, 1)$ 开始飞行，并最终停留在某个格子 $(i, j)$；
• 若一门火炮位于第 $j$ 列、第一行上方，并向下发射一个 1，则该 1 从格子 $(1, j)$ 开始飞行，并最终停留在某个格子 $(i, j)$。

例如，考虑以下发射序列：

1. 发射第 2 行的火炮；
2. 再次发射第 2 行的火炮；
3. 发射第 3 列的火炮。

你手头有一份此次军事训练的报告。该报告是一个边长为 $n$ 的方阵，仅由 0 和 1 构成。你不禁疑惑：这份报告所描述的情形是否真实发生过？换言之，是否存在某种发射序列，使得训练结束后恰好得到该给定矩阵？

每门火炮均可发射任意多次。训练开始前，多边形中每个格子均含有 0。

The first line contains an integer $t$ ($1 \le t \le 1000$) — the number of test cases. Then $t$ test cases follow.

Each test case starts with a line containing an integer $n$ ($1 \le n \le 50$) — the size of the polygon.

This is followed by $n$ lines of length $n$, consisting of 0 and 1 — the polygon matrix after the training.

The total area of the matrices in all test cases in one test does not exceed $10^5$.

第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 测试用例的数量。随后是 $t$ 个测试用例。

每个测试用例以一行开始，该行包含一个整数 $n$（$1 \le n \le 50$）—— 多边形的大小。

接下来是 $n$ 行，每行长度为 $n$，由字符 0 和 1 组成——即训练后的多边形矩阵。

所有测试用例中矩阵的总面积（即所有矩阵元素个数之和）不超过 $10^5$。

For each test case print:

• YES if there is a sequence of shots leading to a given matrix;
• NO if such a sequence does not exist.

The letters in the words YES and NO can be printed in any case.

对每个测试用例，输出：

• 若存在一系列射击操作能得到给定矩阵，则输出 YES；
• 若不存在这样的射击操作序列，则输出 NO。

单词 YES 和 NO 中的字母可以以任意大小写形式输出。

The first test case was explained in the statement.

The answer to the second test case is NO, since a 1 in a cell ($1, 1$) flying out of any cannon would continue its flight further.

第一个测试用例已在题目描述中说明。

第二个测试用例的答案为 NO，因为位于单元格 $(1, 1)$ 的数字 1 若从任意一门大炮射出，其飞行路径将一直延续下去。