Grid Separator

You are given a connected undirected graph G=(V, E). Here V is the set of vertices and E is the set of edges. If removing a subset S of V leaves exactly two connected components, W and B, then S is called a separator. When a vertex is removed, every edge incident to it is removed as well. We write this situation as [S, W, B].

This problem considers separators in a grid graph. Each grid point is a vertex, and each vertex is adjacent to up to eight neighboring vertices: horizontal, vertical, and diagonal. You may think of W as the white region, S as the gray region, and B as the black region.

The initial separator S satisfies these conditions.

1. No proper subset of S is also a separator.
2. S contains one vertex in the top row and one vertex in the bottom row, excluding the four corners.
3. If S is followed from top to bottom, it never moves upward after moving downward.

You may transform S in the following two steps.

1. Choose any number of vertices from B and add them to S. For every chosen vertex, the vertex immediately to its left must belong to S.
2. Remove any number of vertices that originally belonged to S and put them into W. Vertices newly added in step 1 cannot be removed.

After these steps, S must still be a separator. Minimize the size of S.

The input contains multiple test cases.

The first line of each test case contains two integers N and M, the grid dimensions. The grid has size N x M, and 3 <= N, M <= 200.

Each of the next N lines contains a string of length M. Each character is one of S, W, and B, indicating the set containing that vertex. Every W lies to the left of S. The input is guaranteed to be valid.

The input ends with 0 0.

For each test case, print one line containing the minimum possible size of S.