题目描述

想象你现在有一棵树，然后你现在把这个树上任意两点的距离以矩阵的方式写了下来。但是这个矩阵里面可能有一些距离是不合法的，也就是说这个矩阵不能对应一棵带权树。

给定一个矩阵 $M, M_{i, j}$ 表示树上编号为 $i$ 的节点与编号为 $j$ 的节点的距离。判断这个矩阵能否还原成一棵树，使得树上任意两点 $i, j$ 之间的距离为 $M_{i, j}$ 。请注意你还原出来的树边权应为正整数。

输入格式

输入有多组数据。

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

接下来一行为一个整数 $n$ ，表示当前需要还原的树的点数。

接下来 $n$ 行每行 $n$ 个非负整数，表示距离矩阵。

输出格式

对于每组数据，如果可以则输出＂YES＂，否则输出＂NO＂。

样例

样例输入

4
3
0 2 7
2 0 9
7 9 0
3
0 1 1
1 0 1
1 1 0
2
0 0
0 0
2
1 1
0 0

样例输出

YES
NO
NO
NO

数据范围与提示

对于 $30 \%$ 的数据，$n \leq 10$ 。

对于 $70 \%$ 的数据，$n \leq 200$ 。

对于 $100 \%$ 的数据，$n \leq 1000, T \leq 4,0 \leq M_{i, j} \leq 10^9$ 。