Description

在森林里住着一群羊，因为经常有狼光顾，于是羊群们构建了一些防御用的洞穴。当狼来袭的时候，用于躲避狼群。为了让问题简化，假设森林是一个n*m的矩阵，每只羊跟防御洞穴都在一个1*1的矩阵里，每次移动只能到上下左右四个相连的1*1矩阵里。由于洞穴很小，只能容纳一只小羊。问当前情况，所有的小羊都躲入防御洞穴，最少需要多少多少步数。

Input

第一行2个正整数n,m。表示森林为n*m的矩阵
接下来的n行，每行包含m个字符。‘s’表示羊，‘H’表示防御洞穴,‘ . ’表示表示空地。

Output

输出所有的羊都躲入洞穴的最小时间。（每只羊的时间的总和）

Sample Input

5 5
HH..s
.....
.....
.....
ss..H
7 8
...H....
...H....
...H....
sssHssss
...H....
...H....
...H....

Sample Output

10
28

HINT

Source

NBU OJ