For your birthday, you have received Marcia the android and an square grid maze. Once turned on, Marcia repeats this sequence of moves indefinitely: move squares forward, then turn right. Marcia has human-like emotions, so you don't want to crash her into the maze's walls, and neither do you want her to move out of the maze. What is the largest possible such that there is a valid starting square to place Marcia on so that when you turn it on, it will never crash into walls or move out of the maze?

#### Input Specification

The first line of input will contain the integer .

The next lines each contain characters that describe the maze. `.`

indicates a free space and `#`

indicates a wall. There will be at least one empty space in the maze.

#### Constraints

##### Subtask 1 [30%]

##### Subtask 2 [30%]

##### Subtask 3 [40%]

#### Output Specification

Output the largest required by the problem statement.

#### Sample Input

```
5
.....
#.##.
.....
.#.#.
#....
```

#### Sample Output

`2`

#### Explanation of Output for Sample Input

You can place Marcia at the bottom right corner.

## Comments

This comment is hidden due to too much negative feedback. Show it anyway.

Your code, when submitted in PyPy2, still TLEs. It's not guaranteed that Python can be used to solve all problems, and in any case it seems to be an issue with your solution, as a successful Python submission has been made. If you need any more help, leave a reply.

This comment is hidden due to too much negative feedback. Show it anyway.

preprocessing will allow you to determine, in constant time, whether an arbitrary horizontal/vertical line segment contains a

`#`

.