该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

锐神最近在学图论。

Description

假设这里有一个由n个节点的树，他定义两个节点的距离位两个连接两个节点的简单路径上的边数（在一棵树中链接两个点的简单路径是唯一的）。

锐神给出了一个n*n的矩阵D，$D_{i,j}$(矩阵D第 i 行第 j 列的数）表示 点 i 到点 j 的距离。如果$D_{i,j}$ = 0，表示（i，j）的距离位偶数，如果$D_{i,j}$=1，表示（i，j）间的距离为奇数。

锐神想知道是否存在一个合法的树，满足矩阵D的描述。

Format

Input

第一行一个整数 T ( 1 $\le$ T $\le$ 10 ) ，表示测试组数。 接下来 T 组数据，每组数据描述如下：

第一行一个整数 n ( 2 $\le$ n $\le$100 )表示节点数。

接下来n行来描述矩阵 D 。 每行一个长度为n的01组成的字符串。 第i行第j列的数表示 $D_{i,j}$ 。

Output

对于每一组测试数据，如果存在一个合法满足条件的树则输出“Yes”，否则输出“No”。

Samples

2
3
010
101
010
2
11
10

Yes
No

Limitation

1s, 1024KiB for each test case.