Marcus is stuck in a -dimensional grid of size , consisting of `.`

for walkable spaces and `#`

for unwalkable spaces! He is at the top left corner (position and must travel to the bottom right corner (position ) through only walkable spaces. He can **only move** left, right, and down. In a path, let be the number of times he moves down, left, and right, respectively. Let the *cost* of the path be . Marcus wants to find a path from to that has the minimum *cost*.

Marcus wants to know the minimum possible cost. Please help him!

#### Input Specification

The first line will contain the integer , the size of the grid.

The next lines will each contain characters, either `.`

for a walkable space or `#`

for an unwalkable space. The first character of the first line will be position and the character of the line will be position .

It is guaranteed positions and will be walkable (`.`

).

#### Output Specification

Output the minimum *cost* path for Marcus. If there is no path, output `-1`

.

#### Subtasks

##### Subtask 1 [25%]

##### Subtask 2 [75%]

No further constraints.

#### Sample Input

```
6
......
.#....
##.##.
......
.#####
......
```

#### Sample Output

`78`

#### Explanation For Sample

The minimum *cost* path consists of moving down units, left units, and right units, for a total of .

## Comments

>:(

every

day

Marcus

strays

further

from

god's

light.

This comment is hidden due to too much negative feedback. Click here to view it.