당신은 $1 \le x,y \le n$인 점 $(x,y)$로 이루어진 $n \times n$ 격자에서 UFO를 조종하고 있다. 일부 점은 통과할 수 없고 (*), 나머지 점은 통과할 수 있다 (.).

처음에는 점 $(1,1)$에 있고, 가능한 한 빨리 $(n,n)$에 도달하려 한다. 점 $(x,y)$에 있을 때, 1초 안에 $(x+1,y)$, $(x,y+1)$, $(x-1,y)$, $(x,y-1)$ 또는 임의의 음이 아닌 정수 $i \le k$에 대한 $f^i(x,y)$로 순간이동할 수 있다. 함수 $f^i(x,y)$는 다음과 같이 정의된다:

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

목적지가 격자 밖에 있거나 통과할 수 없는 점이면 순간이동할 수 없다.

$(n,n)$에 도달하는 데 필요한 최소 시간을 구하여라. $(n,n)$에 도달할 수 없다면 -1을 출력하여라.

입력

입력의 첫 번째 줄에는 두 정수 $n$과 $k$가 주어진다 ($1 \le n,k \le 5000$).

다음 $n$개 줄에는 각각 격자를 나타내는 $n$개의 문자가 주어진다.

점 $(1,1)$과 $(n,n)$은 통과할 수 있음이 보장된다.

출력

$(n,n)$에 도달하는 데 필요한 최소 시간을 나타내는 정수 하나를 한 줄에 출력한다. 도달할 수 없다면 -1을 출력한다.

예제

입력 1

3 2
.*.
.*.
...

출력 1

3

입력 2

3 3
.*.
.*.
...

출력 2

2