당신이 현재 근무 중인 회사는 평평한 조직 구조라는 아이디어를 극한까지 밀어붙이기로 결정했습니다. 모든 직원 쌍 $A$와 $B$에 대하여, $A$가 $B$의 업무를 직접 감독하도록 배정되었거나 $B$가 $A$의 업무를 직접 감독하도록 배정되었습니다. 물론, 이는 한 사람이 매우 많은 직속 상사를 가질 수 있음을 의미합니다. 경영진은 이것이 직원들로 하여금 자신의 업무가 단 한 명의 관리자가 아닌 수많은 사람에게 정말로 중요하다고 느끼게 만들기 때문에 훌륭하다고 말합니다.

하지만 개선의 여지는 항상 존재합니다. 올해의 기업 목표로서, 사람 $A$가 사람 $B$의 직속 상사일 때, $B$ 또한 동시에 $A$의 간접 상사가 되도록 계층 구조를 수정할 것입니다. (우리는 $n > 2$이고 $c_1 = A, c_n = B$이며 각 $i < n$에 대해 $c_i$가 $c_{i+1}$의 직속 상사인 수열 $(c_1, \dots, c_n)$이 존재할 때, $B$가 $A$의 간접 상사라고 말합니다.)

경영진은 이것이 모든 직원이 다른 사람에게 자신의 권력을 남용하기 전에 두 번 생각하게 만들 것이라고 말합니다.

하지만 자신의 부하 직원이 갑자기 자신의 상사로 임명되었다는 사실을 알게 되면 누군가는 다소 불쾌해할 수 있다는 것은 놀라운 일이 아닙니다. 그리고 그러한 결정 중 일부는 다른 것보다 더 많은 원망을 불러일으킬 수 있습니다. 당신의 임무는 직원 간의 관계 중 일부를 뒤집어 이러한 변화에 따른 원망의 합이 최소가 되도록 하여 기업 목표를 달성하는 것입니다.

입력

입력의 첫 번째 줄에는 테스트 케이스의 수 $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"라는 단어를 출력하십시오. 두 번째 줄에는 당신이 뒤집으려는 관계의 수 $k$와 달성된 원망의 합을 각각 정수로 출력하십시오. $k$를 최소화할 필요는 없다는 점에 유의하십시오. 그다음 $k$개의 줄을 출력하며, 각 줄에는 $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