题目描述

给定一个 $n$ 行 $n$ 列的整数矩阵 $A$，且保证 $A$ 中的每个元素的绝对值不超过 $4$。

判断是否存在非负整数 $i$ 满足 $A^i$ 中的元素均为 $0$。

输入格式

本题多测。

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

随后输入 $T$ 组数据。

对于每组数据，第一行输入一个正整数 $n$，表示矩阵大小。

接下来 $n$ 行，每行输入 $n$ 个整数，表示矩阵 $A$。

输出格式

对于每组数据，输出一行一个字符串 YES 或 NO，表示是否存在非负整数 $i$ 满足条件。

3
2
0 -1
0 0
3
-1 0 0
0 1 0
0 0 -1
3
0 0 0
0 -4 0
0 0 0

YES
NO
NO

提示

特殊性质 A：$A_{i,j}$ 在 $-4\sim 4$ 范围内独立均匀随机生成。

特殊性质 B：矩阵 $A$ 中的元素全部相同。

对于所有数据，保证 $T=30$，$1\le n\le 100$，$|A_{i,j}|\le 4$。