Marisa got lost in the forest!
The forest can be represented as a matrix of size $n \times n$:
- `.` represents empty area.
- `#` represents a tree.
- She can only move to empty cell.
Marisa are currently facing South at position $(1, 1)$, and she can escape if she reaches $(n, n)$. Each move, she can move 1 step forward in her current direction or turn left or right by $90$ degrees.
Her broom is so special that only turning cost her $1$ magic power. What is the minimum power required for her to escape from the forest?
### Input
- The first line contains an integer $n$.
- Next $n$ lines represent the forests, each line contains a string of length $n$.
### Output
- Print the amount of power required, or print `-1` if she has to spend the rest of her life eating mushroom in the forest.
### Constraints
- $1 \le n \le 2000$.
### Example
Input:
```
4
....
.##.
..#.
#...
```
Output:
```
2
```
