题目描述

牧场里有一片树林，林子里没有坑．

贝茜很想知道，最少需要多少步能围绕树林走一圈，最后回到起点．她能上下左右走，也能走对角线格子．

牧场被分成$\red{R}$行$\red{C}$列$\red{(1≤}$$\red{R≤}$$\red{50，}$$\red{1≤}$$\red{C≤}$$\red{50)}$．下面是一张样例的地图，其中 "$\red{.}$"表示贝茜可以走的空地， "$\red{X}$"表示树林， "$\red{*}$"表示起点．而贝茜走的最近的路已经特别地用"$\red{+}$"表示出来．

题目保证，最短的路径一定可以找到．

输入格式

第$\red{1}$行输入$\red{R}$和$\red{C}$

接下来$\red{R}$行$\red{C}$列表示一张地图．

地图中的符号如题干所述．

输出格式

输出最少的步数．

样例

输入样例

6 7
.......
...X...
..XXX..
...XXX.
...X...
......*

输出样例

13