题目描述

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

判断是否存在整数 $p$ 满足：对于任意非负整数 $i$，均有 $A^i$ 中的每个元素都不超过 $p$。

输入格式

本题多测。

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

随后输入 $T$ 组数据。

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

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

输出格式

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

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

YES
YES
NO

提示

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

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

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