La empresa para la que trabajas actualmente ha decidido llevar la idea de una estructura organizativa plana al límite: para cada par de empleados $A$ y $B$, o bien $A$ ha sido asignado para supervisar directamente el trabajo de $B$, o bien $B$ ha sido asignado para supervisar directamente el trabajo de $A$. Por supuesto, esto significa que ahora uno podría tener bastantes supervisores directos... lo cual es genial, porque hace que un empleado sienta que su trabajo es realmente importante para muchas personas en lugar de solo para un único gerente, dicen los ejecutivos.

Sin embargo, siempre hay margen de mejora. Como objetivo corporativo para este año, la jerarquía será revisada para asegurar que siempre que una persona $A$ sea supervisada directamente por una persona $B$, entonces $A$ también sea supervisada indirectamente por $B$ al mismo tiempo (decimos que $A$ es supervisada indirectamente por $B$ si existe $n > 2$ y una secuencia $(c_1, \dots, c_n)$ tal que $c_1 = B$, $c_n = A$ y para cada $i < n$, $c_i$ es un supervisor directo de $c_{i+1}$).

Esto asegurará que cualquier empleado se lo piense dos veces antes de decidir abusar de su posición de poder sobre cualquier otra persona, dicen los ejecutivos.

No debería ser una sorpresa, sin embargo, que uno pueda sentirse algo molesto si se entera de que su subordinado ha sido nombrado repentinamente como su supervisor. Y algunas de estas decisiones podrían causar más resentimiento que otras. Tu tarea es cumplir el objetivo corporativo invirtiendo algunas de las dependencias entre los empleados de tal manera que la suma de los resentimientos por estos cambios sea lo más pequeña posible.

Entrada

La primera línea de la entrada contiene el número de casos de prueba $z$ ($1 \le z \le 100$). Siguen las descripciones de los casos de prueba.

La primera línea de cada caso de prueba contiene un único entero $n$ ($1 \le n \le 2000$) – el número de empleados. Los empleados están numerados del 1 al $n$.

Luego siguen $n$ líneas, cada una conteniendo $n$ enteros $d_{i,j}$ ($0 \le d_{i,j} \le 2 \cdot 10^9$). Si el empleado $i$ es un supervisor directo del empleado $j$, entonces $d_{i,j} > 0$ describe el resentimiento que $i$ sentiría si esta dependencia se invirtiera. De lo contrario (es decir, si $j$ es un supervisor directo de $i$ o si $i = j$), $d_{i,j} = 0$.

El número total de empleados en todos los casos de prueba no supera 10000.

Salida

Para cada caso de prueba, produce una solución que asegure que, para cualquier par de empleados $i, j$ ($1 \le i, j \le n, i \neq j$), o bien $i$ será un supervisor directo de $j$ y $j$ será un supervisor indirecto de $i$, o viceversa. Tu solución debe minimizar la suma de los resentimientos que sentirán los empleados. Si existe más de una solución de este tipo, puedes imprimir cualquiera de ellas.

Si no existe ninguna solución, debes imprimir una sola línea que contenga la palabra "NO".

De lo contrario, en la primera línea imprime una sola palabra "YES". En la segunda línea, imprime dos enteros $k$ y $r$ – el número de dependencias entre empleados que pretendes invertir y la suma de resentimientos alcanzada, respectivamente. Ten en cuenta que no necesitas minimizar $k$.

Luego imprime $k$ líneas, cada una conteniendo dos enteros – los identificadores de los empleados $a, b$ ($1 \le a, b \le n, a \neq b$) tales que $a$ es actualmente un supervisor directo de $b$ y su relación debe invertirse. Nunca debes imprimir el mismo par de empleados más de una vez.

Ejemplos

Entrada 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

Salida 1

YES
2 10
4 5
2 4