Description

During the escape, the animals need to pass through a rectangular area of size $R \times C$. They must enter this area from the upper-left corner and leave from the lower-right corner.

To leave faster, the animals pass through one after another, and each one walks in a random path in four directions (up, down, left, right). That is, an animal does not have to choose the shortest path, and it may stay on the same cell multiple times (including the upper-left and lower-right corners).

Each time an animal steps onto a cell, it leaves a footprint. If the current cell already has a footprint, then the animal erases the existing footprint and leaves its own footprint.

Your task is, based on the footprints left in the snow, to find the minimum possible number of animals that could have escaped.

Input Format

The first line contains the two integers $R, C$ mentioned above.

The next $R$ lines each contain $C$ characters describing the rectangular area. The character T means a tiger footprint, B means a bull footprint, and * means untouched snow with no trace of walking.

You may assume that at least $1$ animal passed through the rectangular area, and every animal that enters the area eventually leaves it.

Output Format

Output the minimum possible number of escaping animals.

4 4
TT*T
*TTT
***T
***T

1

3 5
TTBB*
*T*B*
*TTTT

2

7 5
BT***
BTBBB
BTTTB
BBT*B
BBT*B
BBT**
*BBBB

3

Hint

Sample Explanation

Below is a picture explanation for the second sample:

Constraints

Notes

The scoring of this problem follows the original COCI problem setting, with a full score of $110$.

Translated from COCI2019-2020 CONTEST #1 T5 Zoo.

Translated by ChatGPT 5