Get the Nut

Squirrely has lost his lifetime collection of acorns in an unfortunate geyser accident and now he needs your help! Roll the animals around and get Squirrely to the Acorn, but beware! Not all animals are fluffy as they appear to be. Start from your home forest, and continue through the harsh weather of the snow, the scary swamp and the vast wild west! In your journey you will encounter great dangers, but don’t worry! You and Squirrely will be a great team.

Get the Nut is a very cute game as mentioned above. Now Squirrely is in a forest, which can be divided into 6 rows and 8 columns, 48 grids in total. Squirrely wants to get the nut in another grid. However, it is much more difficult than you can image because the forest is full of danger. There are two kinds of other animal in the forest: Mouse and Pig. Pigs are very vicious, they will kill and eat any other animal (except Pigs, of course) in the adjacent grids. Here “adjacent” means two grids share a common edge. Once any other animal enter grids adjacent to a Pig, it will stop and be eaten. Once an animal is adjacent to the nut, it will stop and eat the nut. So if Squirrely is eaten by a Pig or the nut is eaten by a Pig or a Mouse, the game is over and you fail. At the beginning of the game, each animal occupies one grid. For each step, you can choose one animal to roll in either up, down, left or right direction, the animal will keep rolling until it reach the border of the forest or hit a tree or an animal. Your task is to calculate the minimal number of steps should be made that Squirrely can get the nut.

There are multiple test cases. Please process till EOF.

Each test case gives the map of the forest, which has 6 rows and 8 columns. Each grid of the map is one of the following six characters:

1. '.' - the empty area which every animal can stay or go through
2. '#' - the tree which is an obstacle
3. 'S' - the Squirrely
4. 'M' - a Mouse
5. 'P' - a Pig
6. 'N' - the nut which the Squirrely want to get

You should notice that there is one blank line before every test case. You may assume that there is one and only one nut in the forest and the number of animals in the forest will not exceed 5, and the input guarantees that there are at most 32 empty grids(including the original grids occupied by animals) in the map.

For each test case, output a positive integer indicating the desired answer. You may assume that there is always exists a solution to get the nut, and the minimal number of steps should be made will not exceed 30.

#......N
###.####
###M####
###.####
###.####
###S####

########
###.####
##.....#
#S.M.P.N
########
########

########
S...M.##
####M.##
####M.##
###P..##
####N.##

P.....M#
...##..#
P..##..#
.###...#
..N#...#
.###..S#

4
4
5
15

1. When a Mouse or Squirrely is adjacent to a Pig and a nut at the same time, it will be eaten by the Pig first.
2. At the beginning of the game, it’s guaranteed that you can’t win or fail at once.
3. When being able to eat or be eaten, the animal will stop and finish the eating process.



Sample Explanations

Case #1:
1. roll the Mouse at grid (3, 4) up to grid (1, 4).
2. roll the Mouse at grid (1, 4) left to grid (1, 2).
3. roll Squirrely at grid (6, 4) up to grid (1, 4).
4. roll Squirrely at grid (1, 4) right to grid(1, 7) and he can get the nut.

Case #2:
1. roll the Pig at grid (4, 6) up to grid (3, 6).
2. roll the Pig at grid (3, 6) left to grid (3, 4), why grid (3, 4)? Because it will stop to eat the Mouse at grid (4, 4).
3. roll the Pig at grid (3, 4) up to grid (2, 4), you must roll the Pig to grid (2, 4), otherwise, Squirrely will certainly be eaten by the Pig!
4. just roll Squirrely at grid (4, 2) right to grid (4, 7) and he can get the nut.

Case #3:
1. roll the Mouse at grid (4, 5) down to grid (5, 5), and it is eaten by the Pig, notice that the Mouse at grid(5, 5) can not eat the nut because the Mouse will be eaten by the Pig before it can eat the nut!
2. roll the Mouse at grid (3, 5) down.
3. roll the Mouse at grid (2, 5) down.
4. roll Squirrely at grid (2, 1) right to grid (2, 6).
5. roll Squirrely at grid (2, 6) down to grid (6, 6) and he can get the nut.

2014 ACM/ICPC Asia Regional Xi'an Online