Gustavo ha obtenido un trabajo de cartero en un pequeño pueblo en las montañas. El pueblo puede ser representado por una matriz de \(N×N\) campos. Cada campo contiene exclusivamente una de las siguientes cosas: una casa denotada \(‘K’\), la oficina de correo denotada por \(‘P’\), o pasto denotado por \(‘.’\). Adicionalmente, a cada campo se le asigna una altitud.

Cada mañana, Gustavo entrega la correspondencia a todas las casas en el pueblo. El comienza en el campo denotado por \(‘P’\), el cual representa la oficina de correos del pueblo. A Gustavo le está permitido moverse horizontalmente, verticalmente y diagonalmente, solamente a los cuadros adyacentes. Una vez que el entrega el último paquete, el tiene que retornar a la oficina de correo.

Gustavo no tiene idea de cuan agotador será su trabajo. La diferencia entre las alturas del campo más alto y el más bajo visitados mientras él entrega la correspondencia será igual a su cansancio. Ayúdelo y determine el más pequeño agotamiento para Gustavo mientras él entrega toda la correspondencia.

Entrada

La primera línea de la entrada contiene un entero ~N (2 \le N \le 50)~. Las siguientes ~N~ líneas representan campos en la correspondiente fila. El carácter \(‘P’\) aparecerá exactamente una vez, mientras el carácter \(‘K’\) aparecerá al menos una sola vez. Cada una de las siguientes ~N~ líneas, contiene ~N~ enteros positivos, las altitudes de los campos en las correspondientes filas. Esos valores son menores que ~1 000 000~.

Salida

La salida contiene en un línea simple solamente un entero, el cual representa el mínimo posible de cansancio.

Ejemplo # 1 de Entrada

2
P.
.K
2 1 
3 2

Ejemplo # 1 de Salida

0

Ejemplo # 2 de Entrada

3
P..
.KK
...
3 2 4
7 4 2
2 3 1

Ejemplo # 2 de Salida

2

Ejemplo # 3 de Entrada

3
K.P
...
K.K
3 3 4
9 5 9
8 3 7

Ejemplo # 3 de Salida

5

Explicación del primer ejemplo: Comenzando en la oficina de correos, Gustavo puede moverse directamente al campo con la casa, entregar la correspondencia y regresar a la oficina de correos. Ya que el campo con la oficina de correo y el campo con la casa tienen la misma altitud, el cansancio de Gustavo es igual a cero.