Problem Statement

There is a grid with $N$ rows and $N$ columns. Let $(i, j)$ $(1 \leq i \leq N, 1 \leq j \leq N)$ denote the cell at the $i$-th row from the top and the $j$-th column from the left. Each cell is initially painted red or blue, with cell $(i, j)$ being red if $c_{i,j}=$R and blue if $c_{i,j}=$B. You want to change the colors of some cells to purple so that the following two conditions are simultaneously satisfied:

Condition 1: You can move from cell $(1, 1)$ to cell $(N, N)$ by only passing through cells that are red or purple. Condition 2: You can move from cell $(1, N)$ to cell $(N, 1)$ by only passing through cells that are blue or purple.

Here, "You can move" means that you can reach the destination from the starting point by repeatedly moving to a horizontally or vertically adjacent cell of the relevant colors.

What is the minimum number of cells that must be changed to purple to satisfy these conditions?

Constraints

• $3 \leq N \leq 500$
• Each $c_{i,j}$ is R or B.
• $c_{1,1}$ and $c_{N,N}$ are R.
• $c_{1,N}$ and $c_{N,1}$ are B.
• $N$ is an integer.

Input

The input is given from Standard Input in the following format:

N
c_{1,1}c_{1,2}\cdotsc_{1,N}
c_{2,1}c_{2,2}\cdotsc_{2,N}
\vdots
c_{N,1}c_{N,2}\cdotsc_{N,N}

Output

Print the answer.