Joshua is a very dedicated cosplayer when it comes to Halloween costumes. Last year, he cosplayed as an Anime character, and decided that he would only speak Japanese for the entire day (No one understood what he was saying. Not even his Japanese friends).

Joshua has recently gotten into chess, so he decided to dress up as a knight from chess!

As per his dedication, he decided that this year, he would only trick-or-treat in a very specific way: He will only allow himself to trick-or-treat at a neighbourhood that is in an L-shaped path from his current location.

For example, below is top-down picture of Joshua's city. if J is Joshua's current location, he can travel to any of the neighbourhoods that are marked with a X.

However, Joshua overlooked one slight, yet very important detail: He hasn't even purchased his costume!

Trick-or-treating is about to begin, and he would look absolutely ridiculous showing up to peoples' doors without a costume on, so he must first go to the costume store, to purchase his costume, and then return home.

Because Joshua isn't wearing his costume on the way to the costume store, he is allowed to travel however he wants. However, as soon as he reaches the costume store and puts on his knightly armor, he must then travel in L-shaped paths.

Assuming it takes Joshua 1 minute to travel from one neighbourhood to an adjacent neighbourhood (he can't move diagonally), and that the costume store will always be reachable by exclusively using L-shaped paths, how long will Joshua need to go to the costume store, put on his costume, and get back home?

Constraints

~3\le N \le 1,000~

Input Specification

The first line will contain one integer, ~N~, the length and width (in neighbourhoods) of Joshua's city.

The next ~N~ lines will each contain a string of length ~N~, with . representing a neighbourhood in the city, H representing Joshua's home (his starting position), and S representing the costume store.

Output Specification

Output one integer, the number of minutes it'll take for Joshua to obtain his costume and return home.

Note that it is guaranteed that the costume store will be reachable by exclusively using L-shaped paths.

Sample Input

5
..S..
.....
.....
.....
..H..

Sample Output

10

Sample Output Explanation

On his way to the costume store, Joshua can take whichever way he likes, so he takes the shortest path to the costume store. This maneuver takes 4 minutes.

However, on his way back, he must follow an L-shaped path. This maneuver takes 6 minutes, which results in a total time of 10 minutes.