Северная экспедиция движется по ледяной пустоши, разбитой на квадратные участки размером n × n. Каждый участок либо безопасен для прохода, либо непроходим из-за трещин и торосов.

Караван должен пройти от северо-западного участка (0, 0) к юго-восточному участку (n - 1, n - 1).

Для каждой клетки карты задано значение:

• 0 — безопасный участок, по нему можно пройти;
• 1 — непроходимый участок.

За один переход караван может переместиться из текущего участка в любой соседний по стороне или по диагонали, то есть всего возможно до 8 направлений.

Путь называется допустимым, если:

• все посещённые участки безопасны;
• каждый следующий участок в пути является одним из 8 соседей предыдущего.

Длина пути — это количество участков в этом пути.

Требуется определить длину кратчайшего допустимого пути от (0, 0) до (n - 1, n - 1). Если такого пути не существует, выведите -1.

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

В стандартном вводе записано целое число n — размер карты.

Далее следуют n строк, в каждой из которых записано n целых чисел 0 или 1 — описание ледяной пустоши.

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

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

Ограничения

• 1 <= n <= 100
• grid[i][j] равно 0 или 1

Примеры

Пример 1

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

3
0 1 1
1 0 1
1 1 0

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

3

Пример 2

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

7
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

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

7