E. 多边形
时间限制：2 秒
内存限制：256 兆字节

Polygon 不仅是开发问题的最佳平台，也是一个边长为 $n$ 的方阵，初始时所有单元格都填充字符 0。

在多边形上进行了军事训练。士兵们在第一行的每个单元格上方放置了一门大炮，并在第一列的每个单元格左侧放置了一门大炮。因此，总共放置了 $2n$ 门大炮。

大炮发射字符 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。

输入
第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 测试用例数。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 50$）—— 多边形的边长。

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

所有测试用例中矩阵的总面积不超过 $10^5$。

输出
对于每个测试用例，输出：

• "YES"：如果存在一个射击序列能得到给定的矩阵；
• "NO"：如果不存在这样的序列。

YES 和 NO 的字母可以任意大小写。

样例
输入

5
4
0010
0011
0000
0000
2
10
01
2
00
00
4
0101
1111
0101
0111
4
0100
1110
0101
0111

输出

YES
NO
YES
YES
NO

说明

• 第一个测试用例已在题目描述中解释。
• 第二个测试用例答案为 NO，因为单元格 $(1,1)$ 中的 1 无论从哪门大炮发射，都会继续向前飞行。