SPOJ in Gyumri

   Вовочка нашел кусочек белого кирпича и решил поиграть в интересную игру, которую придумал сам. При помощи кирпича он нарисовал на асфальте квадратное поле, разбитое N на N квадратов. Затем некоторые квадраты он старательно заштриховал.

   После всего Вовочка встал в самый верхний левый квадрат. Теперь он хочет добраться до самого нижнего правого квадрата. При этом Вовочка не может становиться на заштрихованные квадратики. Перемещаться Вовочка может только в соседние квадраты(те которые имеют общую сторону с квадратиком в котором находится Вовочка).

   Ваша задача помочь Вовочке определить какое минимальное число квадратов ему придется посетить, чтобы добраться до цели. Гарантируется, что добраться до цели всегда возможно.

Входные данные.

   Первая строка содержит одно целое число N (2≤N≤50). Далее следует описание поля, N строк по N цифр в каждой (1 — заштрихованный квадрат, 0 — не заштрихованный квадрат).

Выходные данные.

   Одно число — минимальное число квадратов, которое следует посетить Вовочке, чтобы добраться до цели.

Пример.