Mina

Nossa mina de ouro será representada por $N$ linhas e $N$ colunas de quadrados. O mineiro está no quadrado inicial (superior esquerdo) e precisa cavar até o quadrado final (inferior direito), onde existe a maior concentração de ouro da mina. Alguns quadrados, porém, estão bloqueados por pedras, o que dificulta o trabalho. Sabendo que o mineiro pode realizar apenas movimentos ortogonais, seu programa deve calcular o número mínimo de quadrados bloqueados pelos quais o mineiro tem que passar para chegar no quadrado inferior direito. Os quadrados inicial e final nunca estão bloqueados. A figura abaixo ilustra três possíveis minas, para $N=8$, para as quais os números mínimos de quadrados bloqueados são, respectivamente, três, zero e nove. A figura também mostra três possíveis trajetórias mínimas, como exemplo.

Entrada

A primeira linha da entrada contém um inteiro $N$, $2 \leq N \leq 100$, representando as dimensões da mina. Cada uma das N linhas seguintes contém $N$ inteiros, definindo os quadrados da mina. O inteiro 0 representa um quadrado livre e o inteiro $1$, um quadrado bloqueado.

Saída

Seu programa deve produzir uma única linha, contendo um único inteiro, o número mínimo de quadrados bloqueados pelos quais o mineiro tem que passar para chegar no quadrado final.

Exemplos

Exemplo de entrada 1

6
0 1 0 0 0 0
1 1 0 0 1 1
1 0 1 1 1 1
0 0 0 1 1 0
0 0 1 1 1 0
0 1 0 0 0 0

Exemplo de saída 1

3

Exemplo de entrada 2

2
0 0
1 0

Exemplo de saída 2

0