Firma, w której obecnie pracujesz, postanowiła doprowadzić ideę płaskiej struktury organizacyjnej do granic możliwości: dla każdej pary pracowników $A$ i $B$, albo $A$ został wyznaczony do bezpośredniego nadzorowania pracy $B$, albo $B$ został wyznaczony do bezpośredniego nadzorowania pracy $A$. Oczywiście oznacza to, że można mieć teraz całkiem sporo bezpośrednich przełożonych... co jest świetne, ponieważ sprawia, że pracownik czuje, iż jego praca jest naprawdę ważna dla tak wielu osób, a nie tylko dla jednego menedżera, twierdzą dyrektorzy.

Zawsze jednak jest miejsce na poprawę. Jako cel korporacyjny na ten rok, hierarchia zostanie zrewidowana, aby zapewnić, że kiedy osoba $A$ jest bezpośrednio nadzorowana przez osobę $B$, to $A$ jest jednocześnie pośrednio nadzorowana przez $B$ (mówimy, że $A$ jest pośrednio nadzorowana przez $B$, jeśli istnieje $n > 2$ oraz ciąg $(c_1, \dots, c_n)$ taki, że $c_1 = B$, $c_n = A$ oraz dla każdego $i < n$, $c_i$ jest bezpośrednim przełożonym $c_{i+1}$).

Dyrektorzy twierdzą, że zapewni to, iż każdy pracownik dwa razy zastanowi się, zanim zdecyduje się nadużyć swojej pozycji władzy wobec kogokolwiek innego.

Nie powinno być jednak zaskoczeniem, że można poczuć się nieco zirytowanym, jeśli dowie się, że ich podwładny został nagle mianowany ich przełożonym. Niektóre takie decyzje mogą powodować większy żal niż inne. Twoim zadaniem jest zrealizowanie celu korporacyjnego poprzez odwrócenie niektórych zależności między pracownikami w taki sposób, aby suma żalu wynikającego z tych zmian była jak najmniejsza.

Wejście

Pierwsza linia wejścia zawiera liczbę przypadków testowych $z$ ($1 \le z \le 100$). Następnie następują opisy przypadków testowych.

Pierwsza linia każdego przypadku testowego zawiera pojedynczą liczbę całkowitą $n$ ($1 \le n \le 2000$) – liczbę pracowników. Pracownicy są ponumerowani od 1 do $n$.

Następnie następuje $n$ linii, z których każda zawiera $n$ liczb całkowitych $d_{i,j}$ ($0 \le d_{i,j} \le 2 \cdot 10^9$). Jeśli pracownik $i$ jest bezpośrednim przełożonym pracownika $j$, to $d_{i,j} > 0$ opisuje żal, jaki $i$ odczułby, gdyby ta zależność została odwrócona. W przeciwnym razie (czyli jeśli $j$ jest bezpośrednim przełożonym $i$ lub jeśli $i = j$), $d_{i,j} = 0$.

Łączna liczba pracowników we wszystkich przypadkach testowych nie przekracza 10000.

Wyjście

Dla każdego przypadku testowego przygotuj rozwiązanie, które zapewnia, że dla każdej pary pracowników $i, j$ ($1 \le i, j \le n, i \neq j$), albo $i$ będzie bezpośrednim przełożonym $j$ i $j$ będzie pośrednio nadzorowany przez $i$, albo odwrotnie. Twoje rozwiązanie powinno minimalizować sumę żalu, jaki odczują pracownicy. Jeśli istnieje więcej niż jedno takie rozwiązanie, możesz wypisać dowolne z nich.

Jeśli rozwiązanie nie istnieje, powinieneś wypisać pojedynczą linię zawierającą słowo „NO”.

W przeciwnym razie, w pierwszej linii wypisz pojedyncze słowo „YES”. W drugiej linii wypisz dwie liczby całkowite $k$ oraz $r$ – odpowiednio liczbę zależności między pracownikami, które zamierzasz odwrócić, oraz osiągniętą sumę żalu. Zauważ, że nie musisz minimalizować $k$.

Następnie wypisz $k$ linii, z których każda zawiera dwie liczby całkowite – identyfikatory pracowników $a, b$ ($1 \le a, b \le n, a \neq b$) takich, że $a$ jest obecnie bezpośrednim przełożonym $b$ i ich relacja powinna zostać odwrócona. Nigdy nie powinieneś wypisywać tej samej pary pracowników więcej niż raz.

Przykład

Wejście 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

Wyjście 1

YES
2 10
4 5
2 4