FLY又来到了一篇森林，他必须穿过这片森林。为了能安全地离开，FLY要按照守护神Miku们的要求，在森林寻找葱并带给所有的Miku，然后到达终点，才能离开森林。

**说明：**

1. 森林可以看做是直角坐标系，并按 x、y 轴上的单位长度划分成了 N \times M 块，"S"是起点，"T"是终点。

2. "." 是可通行位置，"#" 是障碍物，障碍物的位置不能走，除了障碍物之外的所有位置FLY均可通行。

3. 在森林有多处位置有葱，每个位置可以无限拔葱，用O表示葱的位置。注意FLY最多只能拿得动一根葱。

4. Miku们分布在森林的各个角落（位置不会重叠，最多不超过16只），用M表示MIKU们的位置

为了确保不会迷路，FLY只向上下左右四个方向移动，每次移动要一天。

你能计算一下，最少需要多少天才能完成任务（将葱交给所有的Miku） 

第一行n，m

接下来n行字符串，每行m个字符，表示状态，包括：

（"."、"#"、"M"、"O"、"S"、"T"，含义如题）

最少天数，若无法到达终点或完成任务则输出-1.

数据范围：

n, m \leq 100

miku的数量 \leq 16

S 和 T 的数量各只有1个

保证森林在有MIKU时，必定有葱