Fix the Pond

A shrimp farm uses a rectangular pond laid out as a grid of unit square cells, each cell one meter on a side. For a given integer $N$, the pond has $2N$ rows and $2N+1$ columns. Inside the pond there are exactly $(2N-1)\times N$ barriers, each two meters long, used to temporarily divide the pond into smaller sections for breeding different kinds of shrimp.

The middle point of each barrier is fixed at integer coordinates $(a, b)$, where $0 < a < 2N$ and $0 < b < 2N+1$, and $a$ and $b$ are either both odd or both even. A barrier can be rotated around its middle point to change the pond configuration, but a rotation only switches it between two positions, both parallel to the sides of the pond: vertical or horizontal.

At the end of every season the pond is emptied for maintenance and cleaning, and must be reconfigured so that a special machine can sweep the pond floor. The machine starts at the top-left cell, must pass through every cell exactly once, and must finish at the bottom-left cell.

Given a pond configuration, write a program that determines the minimum number of barrier switches needed to reconfigure the pond as described above. There is always at least one way to reconfigure the pond as required.

The input consists of several test cases and ends at end of file. Each test case is described using several lines.

The first line contains an integer $N$, indicating that the pond has $2N$ rows and $2N+1$ columns ($1 \le N \le 300$). Each of the next $2N-1$ lines contains a string of $N$ characters describing the orientations of the barriers. In the $i$-th line, the $j$-th character gives the orientation of the barrier whose middle point is at $(i, 2j-1)$ if $i$ is odd, or at $(i, 2j)$ if $i$ is even, for $i = 1, 2, \ldots, 2N-1$ and $j = 1, 2, \ldots, N$. The character is the uppercase letter 'V' if the orientation is vertical, or the uppercase letter 'H' if it is horizontal.

For each test case, output a single line with an integer representing the minimum number of barrier switches needed to reconfigure the pond as specified.