Heng crosses the river

Heng wants to cross a river. The river is dotted with islands, and Heng moves from one island to the next by walking over boards that work as bridges. Some islands are already joined by boards, and every board that is already in place lies along the direction of the current. The islands are arranged in an $N \times N$ grid and the current runs down the columns, so an existing board joins two islands that sit directly above each other in the same column. For $N = 3$ the situation may look like this.

While Heng stands on an island, he can take any board that touches that island and turn it 90 degrees around the island, so the board still touches the island after the turn. Turning a board is tiring, so he wants to cross the river with as few 90 degree turns as possible. Turning the same board 90 degrees twice amounts to a 180 degree turn.

At the start Heng has one board on his own bank pointing across, so he can step onto any island of the leftmost column without turning anything. Stepping from an island of the rightmost column onto the far bank also needs a board lying between that island and the bank, and the moment he steps onto it he has crossed the river. In the situation drawn above he can cross with 4 turns like this.

The first line contains $N$ ($2 \le N \le 40$).

Each of the next $N - 1$ lines contains $N$ characters, each of them 0 or 1. The $i$-th of these lines describes the boards between row $i$ and row $i + 1$ of islands, so the second line of the input describes the boards between the top two rows and the last line describes the boards between the bottom two rows. Within a line, the $j$-th character is 1 if a board already joins the $j$-th island of the upper row to the $j$-th island of the lower row, and 0 if no board is there.

Print one integer, the smallest number of 90 degree turns Heng needs to cross the river.