Description

Hace mucho tiempo, en España corría el rumor de la existencia de una ciudad completamente hecha de oro, y que tenia riquezas inimaginables para cualquiera, varios aventureros se adentraron en junglas, desiertos y estepas, siempre guiados por mapas falsos que compraban con mucho dinero.

Maria de Jesús ha encontrado lo que muchos no lograron hallar: el mapa verdaderao y la entrada a la ciudad de oro; que mas bien no es un ciudad de oro, sino una habitación donde el rey ACEMÓN guardaba sus cosas de valor. Con mucho esfuerzo ella ha logrado decifrar el mapa, y lo que a primera instancia parecía ser un laberinto resultó no serlo, ya que al analizarlo mejor se dió cuenta que no había forma de llegar al destino salvo que destruyera algunas paredes. También notó que el laberinto es un cuadrado y que por donde ella puede entrar está representado en la parte superior izquierda del mapa, mientras que el tesoro esta en la parte inferior derecha.

“Guauu!”, exclamó con asombro. Al entrar al laberinto ella encontró que todas las paredes estaban decoradas con imágenes irremplazables; por ello, como buena antropóloga no quiere dañar mas de lo necesario este tesoro de la humanidad. Al ver la orilla del laberinto, se percato que no podía salir de el, ya que estaba hecha de un material lo suficientemente resistente como para no ser destruido con los explosivos que disponía a su alcance.

Ella necesita tu ayuda, sólo quiere que le imprimas el mapa para que se ubique mejor, y le digas cual es el número mínimo de paredes que debe destruir para llegar al tesoro.

Input

Para cada caso de prueba tu recibes un entero n ( 1 ≤ n ≤ 100 ) que es el tamaño del laberinto, y en las siguientes n líneas, recibirás n números Aij (0 ≤ Aij ≤ 19) que indican como está la celda [ i, j ] del mapa. La entrada termina cuando n = 0, este último caso no debe ser procesado.

Para cada valor Aij del mapa, existe una única representación de la forma 10a1 + 5a2 + 3a3 + 1a4, donde a1, a2, a3, a4 son enteros entre 0 y 1.

Si a1 = 1 entonces existe un muro en el norte de la celda.
Si a2 = 1 entonces existe un muro en el este de la celda.
Si a3 = 1 entonces existe un muro en el sur de la celda.
Si a4 = 1 entonces existe un muto en el oeste de la celda.

Output

Para cada caso de prueba tu debes imprimir 2n + 2 líneas, en las primeras 2n + 1 líneas son el mapa en el formato que se observa abajo, y en la ultima línea debes imprimir el mínimo número de paredes que debes tirar para llegar al tesoro.

2
11 18
9 19
2
11 15
9 8
4
11 13 10 15
9 19 9 8
11 15 11 15
4 8 9 8
4
19 19 19 19
19 19 19 19
19 19 19 16
19 19 19 9
0

+-+-+
|   |
+ +-+
| | |
+-+-+
1
+-+-+
|   |
+ + +
|   |
+-+-+
0
+-+-+-+-+
|       |
+ +-+ + +
| | |   |
+-+-+-+-+
|   |   |
+ + + + +
|   |   |
+-+-+-+-+
1
+-+-+-+-+
| | | | |
+-+-+-+-+
| | | | |
+-+-+-+-+
| | | | |
+-+-+-+ +
| | | | |
+-+-+-+-+
5

Problemsetter: Rodrigo Burgos Domínguez.