This content is archived!

For the 2018-2019 school year, we have switched to using the WLMOJ judge for all MCPT related content. This is an archive of our old website and will not be updated.

Problem

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 (1 \leq N \leq 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.

H will mark Ash’s home.

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 1

3
P.P
.H.
P.P

Sample Output 1

10

Sample Input 2

5
P..P.
...H.
.....
PP...
.P...

Sample Output 2

14

Editorial

Read only if you are stuck or have already solved the problem.