入力

入力は以下の形式で標準入力から与えられる．

T
N_1
a_{11} ... a_{1N_1}
a_{21} ... a_{2N_1}
:
a_{N_1 1} ... a_{N_1 N_1}
:
:
N_T
a_{11} ... a_{1N_T}
a_{21} ... a_{2N_T}
:
a_{N_T 1} ... a_{N_T N_T}

入力は複数のテストケースからなる．1 行目には，テストケースの個数を表す整数 T ( 1 \leq T \leq 30) が与えられる.
続いて T 個のテストケースが順に与えられる．
t ( 1 \leq t \leq T ) 番目のテストケースでは，はじめの行にグラフの頂点数を表す整数 N_t ( 1 \leq N_t \leq 30)が与えられる．
続く N_t 行にはそれぞれ N_t 個の整数が空白区切りで与えられ， i 行目の j 番目の整数 a_{ij} (1 \leq i,j \leq N_t, -1 \leq a_{ij} \leq 10000 )が -1の場合，頂点 i から頂点 j への経路が存在しないことを表し，そうでない場合は頂点 i から頂点 j への最短距離が a_{ij} であることを表す．

出力

制約を満たす有向グラフが存在する場合にはYES, しない場合にはNOを出力せよ.