연못 정비하기

새우 양식장은 한 변의 길이가 1미터인 정사각형 칸들을 격자 모양으로 늘어놓은 직사각형 연못을 사용한다. 정수 $N$에 대하여 이 연못은 $2N$개의 행과 $2N+1$개의 열로 이루어진다. 연못 안에는 길이가 2미터인 칸막이가 정확히 $(2N-1)\times N$개 있으며, 서로 다른 종류의 새우를 기르기 위해 연못 내부를 잠시 더 작은 구역으로 나누는 데 쓰인다.

각 칸막이의 중점은 정수 좌표 $(a, b)$에 고정되어 있다. 여기서 $0 < a < 2N$이고 $0 < b < 2N+1$이며, $a$와 $b$는 모두 홀수이거나 모두 짝수이다. 칸막이는 자신의 중점을 축으로 회전시켜 연못의 구성을 바꿀 수 있는데, 회전하더라도 항상 연못의 변과 평행한 두 상태, 즉 수직 또는 수평 중 하나만 취할 수 있다.

한 철이 끝날 때마다 연못은 정비와 청소를 위해 비워지고, 특수한 청소 기계가 연못 바닥을 훑을 수 있도록 재구성되어야 한다. 이 기계는 맨 왼쪽 위 칸에서 작업을 시작하여 모든 칸을 정확히 한 번씩 지난 뒤 맨 왼쪽 아래 칸에서 끝나야 한다.

주어진 연못 구성에 대하여, 위 조건을 만족하도록 연못을 재구성하는 데 필요한 칸막이 전환(회전)의 최소 횟수를 구하는 프로그램을 작성하라. 조건을 만족하도록 재구성하는 방법은 항상 하나 이상 존재한다.

입력은 여러 개의 테스트 케이스로 이루어지며 파일의 끝에서 종료된다. 각 테스트 케이스는 여러 줄로 주어진다.

첫 줄에는 연못이 $2N$개의 행과 $2N+1$개의 열을 가짐을 나타내는 정수 $N$이 주어진다 ($1 \le N \le 300$). 이어지는 $2N-1$개의 줄에는 각각 칸막이들의 방향을 나타내는, 길이가 $N$인 문자열이 주어진다. $i$번째 줄의 $j$번째 문자는, $i$가 홀수이면 중점이 좌표 $(i, 2j-1)$에 있는 칸막이의 방향을, $i$가 짝수이면 중점이 $(i, 2j)$에 있는 칸막이의 방향을 나타낸다 (여기서 $i = 1, 2, \ldots, 2N-1$이고 $j = 1, 2, \ldots, N$이다). 방향이 수직이면 대문자 'V', 수평이면 대문자 'H'이다.

각 테스트 케이스마다, 위에서 명시한 대로 연못을 재구성하는 데 필요한 칸막이 전환의 최소 횟수를 나타내는 정수를 한 줄에 출력한다.