Heng의 강 건너기

Heng은 강을 건너려고 한다. 강에는 섬이 흩어져 있고, Heng은 다리 노릇을 하는 판자를 밟고 섬에서 섬으로 옮겨 간다. 이미 판자로 이어진 섬도 있는데, 놓여 있는 판자는 모두 강물이 흐르는 방향을 따른다. 섬은 $N \times N$ 격자로 늘어서 있고 강물은 열을 따라 위에서 아래로 흐르므로, 처음부터 놓여 있는 판자는 같은 열에서 위아래로 맞닿은 두 섬을 잇는다. $N = 3$일 때 상황은 다음과 같을 수 있다.

Heng은 섬 위에 서 있는 동안 그 섬에 닿아 있는 판자를 하나 골라 섬을 축으로 90도 돌릴 수 있다. 돌린 뒤에도 판자는 여전히 그 섬에 닿아 있다. 판자를 돌리는 일은 몹시 고되므로 Heng은 90도 회전을 가장 적게 쓰고 강을 건너려 한다. 같은 판자를 90도씩 두 번 돌리면 180도를 돌린 셈이다.

처음에 Heng은 자기 쪽 강가에 건너편을 향한 판자를 하나 두고 있다. 그래서 판자를 한 번도 돌리지 않고 가장 왼쪽 열의 어느 섬에나 올라설 수 있다. 가장 오른쪽 열의 섬에서 건너편 강가로 내려설 때도 그 사이에 판자가 놓여 있어야 하고, 내려서는 순간 강을 다 건넌 것이 된다. 위 그림의 상황에서는 다음처럼 판자를 네 번 돌려 강을 건널 수 있다.

첫째 줄에 $N$이 주어진다. ($2 \le N \le 40$)

이어지는 $N - 1$개의 줄에는 각각 0 또는 1로 이루어진 문자 $N$개가 주어진다. 그중 $i$번째 줄은 섬의 $i$번째 행과 $i + 1$번째 행 사이에 놓인 판자를 나타낸다. 즉 입력의 둘째 줄은 맨 위 두 행 사이를, 마지막 줄은 맨 아래 두 행 사이를 나타낸다. 한 줄에서 $j$번째 문자가 1이면 위쪽 행의 $j$번째 섬과 아래쪽 행의 $j$번째 섬을 잇는 판자가 이미 놓여 있고, 0이면 놓여 있지 않다.

Heng이 강을 건너는 데 필요한 90도 회전의 최소 횟수를 한 줄에 출력한다.