Ahora pilotas un ovni en una cuadrícula de $n \times n$ formada por puntos $(x,y)$ con $1 \le x,y \le n$. Algunos puntos son intransitables (*) y otros son transitables (.).

Inicialmente estás en el punto $(1,1)$ y quieres llegar a $(n,n)$ lo antes posible. Cuando estás en $(x,y)$, puedes teletransportarte en un segundo a $(x+1,y)$, $(x,y+1)$, $(x-1,y)$, $(x,y-1)$ o a $f^i(x,y)$ para cualquier entero no negativo $i \le k$. La función $f^i(x,y)$ se define como:

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

No puedes teletransportarte si el destino está fuera de la cuadrícula o es intransitable.

Calcula el tiempo mínimo necesario para llegar a $(n,n)$. Si nunca puedes llegar a $(n,n)$, imprime -1.

Entrada

La primera línea de la entrada contiene dos enteros $n$ y $k$ ($1 \le n,k \le 5000$).

Cada una de las siguientes $n$ líneas contiene $n$ caracteres que representan la cuadrícula.

Se garantiza que los puntos $(1,1)$ y $(n,n)$ son transitables.

Salida

Un entero en una línea que represente el tiempo mínimo para llegar a $(n,n)$, o -1 si es inalcanzable.

Ejemplos

Entrada 1

3 2
.*.
.*.
...

Salida 1

3

Entrada 2

3 3
.*.
.*.
...

Salida 2

2