Problem Statement

You are now in a park called Competitive Programming Park.
The grounds of this park are rectangular and divided into a grid of $H\times W$ sections, with $H$ cells in the north-south direction and $W$ cells in the east-west direction.
Hereafter, the section that is $r$-th from the north and $c$-th from the west is called section $(r,c)$.

Starting from section $(1,1)$, you repeatedly move one section south or east, aiming for section $(H,W)$, which is adjacent to the park exit.
Here, moving one section takes you 1 minute (regardless of direction).

Sometimes, a mischievous child may interfere with you.
If you move (by the movement described above) into a section where a mischievous child is waiting, that child carries you to section $(1,1)$,
leaves you there, and then goes back to her home outside the park.
Note that the mischievous child is very fast, so the time it takes for her to carry you to section $(1,1)$ and release you may be regarded as 0 minutes.

Information about the $H\times W$ sections is given as input.
If $a_{i,j}$ is '.', section $(i,j)$ contains nothing; if it is 'k', a mischievous child is waiting in section $(i,j)$.

Let $x$ minutes be the shortest time it takes you to reach section $(H,W)$. Output the value of $x$.

Input

$H\ W$
$a_{1,1}...a_{1,W}$
$:$
$a_{H,1}...a_{H,W}$

• $1 \le H,W \le 2000$
• $(H,W) \ne (1,1)$
• $H,W$ are integers
• $a_{i,j} = $ '.' or $a_{i,j}=$ 'k'
• $a_{1,1}\ne$ 'k'
• $a_{H,W}\ne$ 'k'

Output

Output the value of $x$.
Print a newline at the end.

Sample

2 2
.k
k.

3

5 4
....
kk..
....
..kk
....

8

5 5
..kkk
k.kkk
k..kk
kk.kk
kk...

8

3 4
.kkk
k..k
kkk.

10