あなたが現在働いている会社は、フラットな組織構造という考え方を極限まで推し進めることにしました。すべての従業員のペア $A, B$ について、$A$ が $B$ の仕事を直接監督するように割り当てられているか、$B$ が $A$ の仕事を直接監督するように割り当てられているかのいずれかです。もちろん、これは一人の従業員が非常に多くの直属の上司を持つ可能性があることを意味します。経営陣によれば、これは従業員が自分の仕事がたった一人の上司だけでなく、非常に多くの人々にとって重要であると感じられるため、素晴らしいことだそうです。

しかし、改善の余地は常にあります。今年度の企業目標として、ある人物 $A$ が人物 $B$ に直接監督されているときはいつでも、$A$ が同時に $B$ に間接的にも監督されていることを保証するように階層構造を修正することになりました（$n > 2$ かつ $c_1 = A, c_n = B$ であり、各 $i < n$ について $c_i$ が $c_{i+1}$ の直接の上司であるような数列 $(c_1, \dots, c_n)$ が存在する場合、$A$ は $B$ に間接的に監督されていると言います）。

経営陣によれば、これにより、どの従業員も他の誰かに対して権力を乱用しようと考える前に二度考えるようになるはずだとのことです。

しかし、自分の部下が突然自分の上司に任命されたと知れば、誰でも多少は腹を立てるでしょう。そして、そのような決定の中には、他の決定よりも大きな不満を引き起こすものもあります。あなたのタスクは、従業員間の依存関係の一部を反転させることで、これらの変更による不満の合計が最小になるようにして、企業目標を達成することです。

入力

入力の最初の行には、テストケースの数 $z$ ($1 \le z \le 100$) が含まれます。続いて各テストケースの説明が続きます。

各テストケースの最初の行には、従業員の数を表す単一の整数 $n$ ($1 \le n \le 2000$) が含まれます。従業員には $1$ から $n$ までの番号が付けられています。

続く $n$ 行には、それぞれ $n$ 個の整数 $d_{i,j}$ ($0 \le d_{i,j} \le 2 \cdot 10^9$) が含まれます。従業員 $i$ が従業員 $j$ の直接の上司である場合、$d_{i,j} > 0$ は、この依存関係が反転した場合に従業員 $i$ が感じる不満を表します。それ以外の場合（つまり、$j$ が $i$ の直接の上司である場合や $i = j$ の場合）、$d_{i,j} = 0$ です。

すべてのテストケースにおける従業員の合計数は $10000$ を超えません。

出力

各テストケースについて、任意の従業員のペア $i, j$ ($1 \le i, j \le n, i \neq j$) に対して、$i$ が $j$ の直接の上司であり、かつ $j$ が $i$ の間接的な上司であるか、またはその逆が成り立つような解決策を作成してください。あなたの解決策は、従業員が感じる不満の合計を最小化する必要があります。そのような解決策が複数存在する場合は、そのうちのどれを出力しても構いません。

解決策が存在しない場合は、「NO」という単語を含む単一行を出力してください。

それ以外の場合は、最初の行に「YES」という単語を出力してください。2行目には、反転させる従業員間の依存関係の数 $k$ と、達成された不満の合計 $r$ を出力してください。なお、$k$ を最小化する必要はありません。

続いて $k$ 行を出力し、各行に $2$ つの整数、つまり $i$ が現在 $j$ の直接の上司であり、その関係を反転させるべき従業員の識別子 $i, j$ ($1 \le i, j \le n, i \neq j$) を出力してください。同じ従業員のペアを二度以上出力してはいけません。

入出力例

入力 1

1
5
0 1 0 6 11
0 0 1 6 12
2 0 0 7 12
0 0 0 0 4
0 0 0 0 0

出力 1

YES
2 10
4 5
2 4