teddy online judge

103. Leyendo matrices

Limite de tiempo : 1 seg.   Total runs : 38  Aceptados : 9

Uno de los retos mas interesantes para un estudiante de programación es cuando comienza a aprender y usar matrices y en este concurso no queremos dejarlas fuera.

Dada una matriz de tamaño N*N debes encontrar el tamaño de la secuencia de numeros ascendentes no repetidos mas grande dentro de la matriz.

Existen 4 formas diferentes de recorridos validos:
Comenzando de la posició 0,0 de izquierda a derecha y de arriba a abajo.
Comenzando de la posició N-1,N-1 de derecha a izquierda y de abajo a arriba.
Comenzando de la posició 0,0 de arriba a abajo y de izquierda a derecha.
Comenzando de la posició N-1,N-1 de abajo a arriba y de derecha a izquierda.

Recuerda que cuando llegas al final de una fila y aun hay mas filas estas cuentan como si estubieran unidas, asi que la secuencia puede continuar de una fila a otra, de la misma manera para las columnas.

Entrada

Un entero N que indica el numero de casos de prueba, seguido por N casos. Cada caso consta de un entero P que indica que hay P lineas con P enteros C cada una. 0 ≤ C ≤ 100 y 0 < P ≤ 100000

Salida

N líneas de salida con un entero C que representa el tamaño de la secuencia mas grande encontrada.

Ejemplo entrada

1
5
6 2 5 9 1
8 1 2 3 4
9 4 3 2 1
6 8 3 6 1
9 4 2 6 7

Ejemplo salida

5


Nota: En este caso la secuencia fue 1 2 3 4 9 , puede ser comenzar en 1,1 y terminar en 2,0 ó bien
comenzar en 2,4 y terminar en 2,0