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 ~N~ ~(2 \le N \le 20)~. ~N~ lines follow, each containing ~N~ 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 one P.
• H will mark Ash's home. If is guaranteed there will be exactly one H.

For ~50\%~ of the cases, the number of pokemon will be at most ~10~.

For the remaining cases, the number of pokemon will be at most ~15~.

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