《地下城漫步：纸汤》（Dungeon Crawl: Paper Soup）刚刚成为了最受欢迎的游戏，你准备尝试一下。游戏发生在一个由 $N$ 行 $M$ 列组成的矩形区域内，每个单元格可以是以下类型之一：

• 空单元格 ‘.’；
• 墙 ‘#’；
• 金币单元格 ‘o’；
• 爆炸地雷单元格 ‘X’；
• 起始单元格 ‘S’。

保证第一行、最后一行、第一列和最后一列仅包含墙（注意玩家不能穿过墙单元格）。场地将包含一个或多个起始单元格。游戏开始时，玩家将被放置在标记为 ‘S’ 的起始单元格之一。由于游戏发生在一个能见度降低的地下城系统中，玩家无法看到整个地图，只能看到以其当前位置为中心的 $3 \times 3$ 方格。此外，对于玩家而言，地雷和起始单元格显示为普通空单元格（它们是不可见的）。

每次移动，玩家只能前往北、南、东或西方向的相邻单元格。如果玩家进入一个有金币的单元格，金币会被收集并消失。如果玩家进入一个有爆炸地雷的单元格，地下城系统会坍塌，玩家失去所有已收集的金币，游戏结束。

好消息是你通过浏览多个在线指南获得了地下城的地图。然而，你不知道你的起始位置在哪里——尽管保证你会从其中一个起始单元格开始。如果你进行最优操作，你保证能获得的最大金币数量是多少（同样，在不知道起始位置的情况下）？

输入格式

输入的第一行包含 $N$ 和 $M$，即游戏地图的行数和列数。接下来的 $N$ 行包含地图，每行包含 $M$ 个字符，使用题目描述中定义的表示法。

输出格式

输出仅包含一个数字，即在不知道起始位置的情况下，在相应地图上保证能获得的最大金币数量。

数据范围

• 设 $S$ 为地图上可能的起始单元格数量。
• $N \le 400, M \le 400, S \le 60$。

样例

输入 1

3 7
#######
#Soooo#
#######

输出 1

4

输入 2

3 8
########
#SoXooS#
########

输出 2

1

输入 3

7 18
##################
#................#
#.o...SX.......o.#
#.o...X..X.....o.#
#.o.....XS.....o.#
#................#
##################

输出 3

0

输入 4

7 18
##################
#....#...........#
#.o...SX.......o.#
#.o...X..X.....o.#
#.o.....XS.....o.#
#.........#......#
##################

输出 4

6

输入 5

7 18
##################
#......X..S....oo#
##################
#..o..S.X......o.#
##########X#######
#o.....S...X.....#
##################

输出 5

1

说明

样例 1：只有一个起始位置，因此我们知道玩家将从哪个位置开始。在这种情况下，玩家可以收集地下城中所有可用的金币。

样例 2：有两个起始位置，玩家可以根据从起点看到的内容推断出他们所在的位置（@ 是玩家的位置）：

### ###
#@o o@#
### ###

如果玩家从左侧起始位置开始，最多可以收集 1 枚金币；而从右侧起始位置开始，则可以收集 2 枚金币。因此，在最坏的情况下，我们可以收集 1 枚金币。

样例 3：无论起始位置在哪里，在最坏的情况下，玩家都会踩到地雷并失败。玩家看到的初始区域是：

...
.@.
...

样例 4：根据墙的位置（左上角或右下角），玩家可以确定起始位置并安全地收集所有 6 枚金币。游戏开始时的视野将是以下两种情况之一：

#.. ...
.@. .@.
... ..#

样例 5：玩家向左移动 2 格。如果他们看到金币，那么他们就在第四行，因此他们将获得金币。

否则，玩家仍然不知道他们是在第二行还是第六行，所以他们会向右移动 4 格。如果他们在右上角的单元格看到一个空位（地雷单元格将显示为空单元格），那么他们就在第六行，所以他们会向左移动以捡起金币。

如果他们在右上角没有看到空位，那么玩家将向右移动以捡起 2 枚金币，因为他们是在第二行。因此，最少能收集到的金币数量是 1。

我们可以观察到，先向右走是危险的，因为玩家在从附近单元格获得任何信息之前，可能会从中间行踩到地雷。