Северная экспедиция должна провести караван через ледяную пустошь, представленную квадратной картой размера n × n.

Каждая клетка карты имеет одно из двух состояний:

• 0 — участок льда свободен, по нему можно пройти;
• 1 — участок занесён торосами, пройти через него нельзя.

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

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

• по вертикали,
• по горизонтали,
• по диагонали.

Путь может проходить только через свободные клетки.

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

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

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

В следующих n строках содержится по n чисел 0 или 1 — описание ледяной пустоши.

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

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

Ограничения

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

Примеры

Пример 1

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

2
0 1
1 0

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

2

Пример 2

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

3
0 0 0
1 1 0
1 1 0

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

4

Пример 3

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

3
1 0 0
1 1 0
1 1 0

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

-1