Description

在逃跑的过程中，动物们需要通过一个 $R \times C$ 的矩形区域。它们必须从这片区域的左上角进入，并从右下角离开。

为了更快地离开这里，动物们将一个接着一个地经过，并以一种随机的路径往四个方向（上、下、左、右）行走。也就是说，每一个动物并不一定选择最短路径，而且可能在同一位置停留数次（包括左上角和右下角）。

动物们每踏上一个格子，便会留下脚印。如果当前位置已经有了脚印，那么该动物会擦除当前的脚印，并留下自己的脚印。

你的任务是根据雪地脚印的情况，求出逃跑动物可能的最少数量。

Input Format

第一行包含题中所提到的两个整数 $R,C$。

接下来的 $R$ 行，每行有 $C$ 个字符，表示矩形的区域。其中，字符 T 表示老虎的脚印， B 表示公牛的脚印，* 表示没有行走痕迹的雪地。

你可以认为，至少有 $1$ 个动物经过了矩形区域，并且每个进入矩形区域的动物都最终离开了区域。

Output Format

输出逃跑动物可能的最少数量。

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

样例解释

下列是对第二个样例的图片解释：

数据范围及约定

说明

本题分值按 COCI 原题设置，满分 $110$。

题目译自 COCI2019-2020 CONTEST #1 T5 Zoo 。