Over the summer, Ash fell in love with a new pokemon game where the objective is to catch pokemon in your area. He loved the catching aspect of the game, however he disliked the amount of walking involved to find pokemon. As a result, whenever he would go out on Pokehunts, he would aim to minimize the amount of walking needed to be done.
Given a map of Ash's surroundings and where the Pokemon are located, can you figure out what is the shortest path to visit all the pokemon locations and return back to his home?
Input
The input begins with an integer . lines follow, each containing characters, which provide a map of Ash's surroundings.
.
will mark empty space.P
will mark a pokemon Ash wants to catch. It is guaranteed there will be at least oneP
.H
will mark Ash's home. If is guaranteed there will be exactly oneH
.
For of the cases, the number of pokemon will be at most .
For the remaining cases, the number of pokemon will be at most .
Output
Output one integer, the smallest distance that Ash needs to travel to catch all the pokemon and return home.
Sample Input
3
P.P
.H.
P.P
Sample Output
10
Sample Input
5
P..P.
...H.
.....
PP...
.P...
Sample Output
14
Comments