Robinson's Boat

Tossed by the storm on a deserted island, Robinson built himself a boat so that he could go out to sea and seek human habitation. Being an experienced sailor, he built the boat with proper craftsmanship. In particular, the boat has a longitudinal axis of symmetry (its front and stern are not equally wide – it is thin at the prow, widens gradually toward the centre, and narrows again at the stern) and is initially positioned parallel to one of the cardinal directions. Moreover, at some point in the middle the boat is wider than at both the prow and the stern.

Unfortunately, Robinson launched his boat in waters hemmed in by extremely thick and stiff reed, so that the boat cannot break through by itself. However, by carefully manoeuvring between the obstacles it might reach the high seas. Due to lack of manoeuvrability the boat cannot turn; it can only move one unit step at a time in one of the four cardinal directions (north, south, east, or west). Moves with the stern or the broadside facing the front are allowed.

The island and its surroundings are given as a square map of n × n unit cells. Each cell is either water, part of Robinson’s boat, or an obstacle (land or reed). Initially, the boat is completely placed on water with its boat parts marked, and its longitudinal axis is parallel to one of the cardinal directions. We assume the high seas start immediately outside the map. Robinson may reach the high seas if his boat can completely leave the area depicted by the map.

A single move consists of shifting the boat one cell to a side‐adjacent field. A move is permissible if both before and after the move every cell covered by the boat that lies within the map is water. (When the boat is partially or completely outside the map, cells outside the map are assumed to be safe.)

Your task is to compute the minimum number of moves required for the boat to completely leave the map. If it is impossible, output -1.

Note: All formulas must be written in LaTeX. For example, the map size is given as $n\times n$.

inputFormat

The input is read from standard input and has the following format:

$n$
$line_1$
$line_2$
... 
$line_n$

The first line contains an integer $n$ ($1\le n\le 100$) denoting the side length of the square map. Each of the next $n$ lines contains exactly $n$ characters. Each character is one of the following:

• . representing water,
• r representing a cell occupied by Robinson's boat, or
• # representing an obstacle (land or reed).

It is guaranteed that the boat cells form a connected shape and that the boat is initially placed completely within the map on water.

outputFormat

Output a single integer: the minimum number of moves required for the boat to completely leave the map. If it is impossible, output -1.

sample

7
.......
.......
.......
...r...
.rrrrr.
...r...
.......

6

</p>