Marisa got lost in the forest!
The forest can be represented as a matrix of size n×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≤n≤2000.
### Example
Input:
4...
Output:
2