To build the machine, Ralph and Vanellope needed to find a long lollipop. When they found it, they realized that the only way to return was to go through the labyrinth. And of course, you will have to take a lollipop with you.

The maze is a field of n on m cells. Each cell is either empty or contains a maze wall. In the place that Ralph and Vanellope found, the lollipops come in different lengths, but they all occupy k consecutive cells in one line for some k. Of course, a lollipop cannot be in a cage containing a maze wall. Ralph is very strong, so he can carry any length of lollipop.

Initially, Ralph can enter the maze in any cell in the left column, but he must keep the lollipop parallel to the left edge of the maze. To get out of the maze, he must be in some cell of the right column of the labyrinth, holding the lollipop parallel to this border.

When Ralph holds the lollipop parallel to one of the maze's borders, he can move it one space along that border, or he can grab the candy by one of its ends, lift it up into the air there, and drop it parallel to the other side of the maze. Of course, he can perform these actions only if after these actions the lollipop is on empty cells.

Now Ralph and Vanellope are wondering what is the maximum length of the lollipop that can be carried through the maze.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 300) - the number of rows and columns in the maze respectively. The next n lines contain m characters. j-th character of i-th line is equal to "#" if there is a wall in j-th cell of i-th line, otherwise it is equal to * "."*.

Output

Print one number - the maximum number of cells that candy can occupy, such that Ralph can move it through the maze. If a lollipop of no length can be carried through the maze, print the number 0.