Sgu229 Divide and conquer

给定一个 $N\times N$ 的棋盘，其中放置了若干个 $1\times 1$ 的骨牌。所有骨牌对应的单位方格组成集合 $Q$。

请判断能否将集合 $Q$ 划分成两个互不相交的部分，使其中一部分经过旋转和平移后能够与另一部分完全重合。旋转角度只能是 $90^\circ$ 的整数倍，即 $0^\circ$、$90^\circ$、$180^\circ$ 或 $270^\circ$；旋转后，可以再沿某个向量进行平移。

输入格式

第一行包含一个整数 $T$，表示数据组数。

每组数据的第一行包含一个整数 $N$，表示棋盘大小为 $N\times N$。

接下来 $N$ 行，每行包含一个长度为 $N$ 的字符串，描述骨牌的摆放情况。其中，字符 $1$ 表示对应位置放置了骨牌，字符 $0$ 表示对应位置没有骨牌。

输出格式

对于每组数据输出一行。

如果可以将所有骨牌划分成完全相等的两部分，输出 YES；否则输出 No。

样例输入

2
3
100
110
010
3
000
010
000

样例输出

YES
No

数据范围

• $T\le 20$；
• $N\le 20$。

来源与许可

本题为 SGU 229「Divide and Conquer」，题面与测试数据整理自 BZOJ 1985。

样例 1

输入

2
3
100
110
010
3
000
010
000

输出

YES
No