After exploring an ice cave in a glacier, you begin to head out to find that an avalanche has blocked off the entrance! You head over to the other side of the glacier, where there is an exit. However, there are several chunks of ice blocking your way. The cave can be modelled as a grid with ~R~ rows and ~C~ columns. You begin at the top left of this grid, and need to get to the bottom right cell at row to escape.

At any cell on the grid, you can move directly up, down, left, or right to an adjacent cell, provided that is not blocked off with an ice block. To help you out, you have a special ice-melting gadget that can melt an ice block that occupies a cell, making it free for you to traverse. You may melt a block if you are on a cell adjacent to it. The special heating fluid costs quite a bit, so you'd rather not use it unless you have to. How many times must you use the ice-melting gadget on a block of ice so that you can escape?

Input Specification

The first line contains two spaced integers, ~R~ and ~C~ ~(1 \le R,C \le 10^3)~.

The next ~R~ lines contains a string of ~C~ characters each, where each character is either a . to indicate a free path and # to indicate a blocked path.

It is guaranteed that the starting position will not be blocked.

Output Specification

Output the minimum number of times you must use the ice-melting gadget so that you can escape to the bottom right corner.

Sample Input 1

3 4
..#.
..##
##..

Output for Sample Input 1

1

Explanation of Output for Sample Input 1

One way to create a path is by melting the ice block on the ~3^{\text{rd}}~ row and ~2^{\text{nd}}~ column. There is no way for a path to exist without using the melting gadget.

Sample Input 2

5 5
..#..
.#.#.
#.###
#.##.
.##..

Output for Sample Input 2

2

Explanation of Output for Sample Input 2

One way to create a path is by melting the ice block on the ~1^{\text{st}}~ row and ~3^{\text{rd}}~ column. Then, melt the block on the ~3^{\text{rd}}~ row and ~5^{\text{th}}~ column. There is no way to create a path by melting fewer blocks.

Sample Input 3

1 1
.

Output for Sample Input 3

0