To further celebrate his birthday, Sanjay is at Koala Land with his best friend, Sam. While Sam is on a scary-looking roller coaster that Sanjay didn't want to go on, Sanjay decides to buy him balloons!

Imagine Koala Land as an ~N~ by ~M~ grid. The balloon store is situated at the top left cell, ~(1, 1)~, and Sam will leave the roller coaster at the bottom right cell with coordinates ~(N, M)~. Scattered throughout the grid are amusement rides that serve as obstacles.

Sanjay wants to bring Sam as many balloons as possible, but is limited by the presence of obstacles. A package of ~x~ balloons takes up a square space of ~x~ by ~x~. Balloons, as solid objects, can only move through spaces that are not occupied by obstacles. In other words, if Sanjay takes ~x~ balloons, he can only move through spaces of minimum size ~x~ by ~x~. At any cell, Sanjay is allowed to move up, down, left, or right, as long as the resulting cell is contained in the dimensions of the grid. Given this constraint, what's the maximum number of balloons that Sanjay can bring Sam?

Note that if Sanjay starts with ~x~ balloons, he will initially occupy the square defined by the coordinates ~(1, 1)~, ~(x, 1)~, ~(x, x)~, and ~(1, x)~. Only the bottom right corner of Sanjay's group of balloons must reach ~(N, M)~ for him to reach Sam. Additionally, cells ~(1, 1)~ and ~(N, M)~ will never be blocked.

For this problem, Python users are recommended to use PyPy over CPython.

Constraints

For all subtasks:

~2 \le N, M \le 1500~

Subtask 1 [20%]

~2 \le N, M \le 200~

Subtask 2 [80%]

No additional constraints.

Input Specification

The input will contain ~N~ lines of ~M~ characters, representing the grid as described in the statement.

An obstacle is represented by X and an empty space is represented by O.

Output Specification

Output the maximum number of balloons that Sanjay can bring Sam.

If Sanjay cannot bring Sam any balloons, output ~0~.

Sample Input 1

4 4
OOOX
OOOX
XOOO
XOOO

Sample Output 1

2

Explanation for Sample 1

If Sanjay takes two balloons, he initially occupies the square defined by the coordinates, ~(1, 1)~, ~(2, 1)~, ~(2, 2)~, and ~(1, 2)~. If he moves right, down, down, and finally right, he can reach his destination.

Sample Input 2

4 5
OOOXX
OOOOO
OOOOO
OOOOO

Sample Output 2

3