题目背景

备注：原题（Java）时间限制 3.0s，空间限制 512 MB。

题目描述

俄罗斯方块是一款风靡全球的游戏，在游戏中有多种方格图案，我们只关注这四个经典的方块图案：LITS，如下图所示：

LITS 这四种方块都是由四个相同大小的小方块组成的。 现在给出一副大小为 $N \times N$ 的格子图，每个格子上都有一个数字 $0/1$，如果格子处的数字为 $1$ 说明这个格子上有一个小方块，数字为 $0$ 则没有。 你需要判断从这个格子图上是否可以找出 LITS 四个方块图案（每个方块图案之间都是独立的，不存在不同的图案公用同一个小方块的情况）。其中 LITS 方块的形状旋转任意个 $90^\circ$ 都是合法的，但不允许翻转。

输入格式

第一行一个整数 $T$，表示有 $T$ 组数据。 每组数据的第一行包含一个整数 $N$，表示格子图大小。 接下来输入 $N$ 行，每行 $N$ 个值为 $0/1$ 的整数，表示格子布局。

输出格式

对于每组数据，输出一行包含一个字符串。如果此组数据满足题意则输出 Yes，否则输出 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

提示

【样例解释】

对于样例中的第二个格子图，一种 LITS 的摆放方案如下：

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

【数据范围】

• 对于 $30 \%$ 的评测用例：$1 \leq N \leq 5$。
• 对于 $60 \%$ 的评测用例：$1 \leq N \leq 10$。
• 对于 $100 \%$ 的评测用例：$1 \leq T \leq 10$，$1 \leq N \leq 50$。

【特别备注】

由于讨论情况较多，本题的数据可能存在错误，请大家自由尝试并寻找错误。