The Floor is Lava

Whenever William steps on a floor made with tiles, he plays the "Hot Lava" game. In this game the floor is lava, that is, some of the tiles are to be absolutely avoided.

This particular floor is a $H \times W$ grid made of tiles. Some of those tiles are red, the remaining ones are white. William wants to get from tile $(0, 0)$ to tile $(H − 1, W − 1)$ using only white tiles, as quickly as possible. He can move diagonally from one tile to an adjacent one (by vertex). Moreover, he can move vertically or horizontally from one tile to one that is adjacent by edge, also to the next tile in the same direction, by doing a long jump.

Task

Help William compute the quickest route, as the number of jumps (short or long jumps) needed.

Input data

The first line contains two integers $H$ and $W$, the height and the width of the grid, respectively.

Other $H$ lines follow, each containing a string of $W$ characters (either . or #).

Output data

You need to write a single line with an integer: the minimum number of jumps needed.

Constraints and clarifications

• $1 \leq H,W \leq 1 \ 000$
• The $(0, 0)$ and $(H − 1,W − 1)$ positions in the grid will always contain a . and never a #.
• There will always be some route from $(0, 0)$ to $(H − 1,W − 1)$.

Example 1

stdin

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

stdout

3

Explanation

William could follow the path denoted by o's:

o###
.oo.
###o

Another possible solution:

o###
.o.o
###o

Example 2

stdin

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

stdout

5

Explanation

There is a unique best solution:

o##..
o##..
#o#o.
#.##o
.##.o