You are now piloting a UFO in an $n \times n$ grid formed by points $(x,y)$ where $1 \le x,y \le n$. Some points are impassable (*) and others are passable (.).

Initially, you are at point $(1,1)$, and you aim to reach $(n,n)$ as quickly as possible. When you are at point $(x,y)$, you can teleport to $(x+1,y)$, $(x,y+1)$, $(x-1,y)$, $(x,y-1)$, or $f^i(x,y)$ for any non-negative integer $i \le k$ in one second. The function $f^i(x,y)$ is defined as:

$$ f^i(x,y)=\begin{cases}(x,y)&(i=0),\\f^{i-1}(y+1,x)&(i>0).\end{cases} $$

You cannot teleport if the target location is outside the grid or if the target location is impassable.

Find the minimum time required to reach $(n,n)$. If you can never reach $(n,n)$, print -1.

Input

The first line of the input contains two integers $n$ and $k$ ($1 \le n,k \le 5000$).

Each of the next $n$ lines contains $n$ characters, representing the grid.

It is guranteed that points $(1,1)$ and $(n,n)$ are passable.

Output

One integer in a line representing the minimum time to reach $(n,n)$, or -1 if it is unreachable.

Examples

Input 1

3 2
.*.
.*.
...

Output 1

3

Input 2

3 3
.*.
.*.
...

Output 2

2