건초 더미 뛰어넘기

농부 존은 소들이 게을러져서 다시 체력을 기르게 하려고 한다. 그가 고른 방법은 밭에 건초 더미를 놓고 소가 북서쪽 모서리에서 남동쪽 모서리까지 뛰어가게 하는 것이다. 밭은 $n \times n$ 정사각 격자다. 지도에서 북쪽은 위, 남쪽은 아래, 동쪽은 오른쪽, 서쪽은 왼쪽이다.

소는 동쪽이나 남쪽으로만 똑바로 뛴다. 서쪽이나 북쪽으로는 뛰지 못하고, 남동쪽 같은 대각선 방향으로도 뛰지 못한다. 한 번에 뛰는 거리는 $k$칸으로 제한된다. 즉 한 번의 점프로 같은 행에서 동쪽으로 $1$칸에서 $k$칸까지, 또는 같은 열에서 남쪽으로 $1$칸에서 $k$칸까지 이동한다. 뛰어넘는 도중에 지나가는 칸은 건초 더미여도 되고 빈 칸이어도 되며, 사이에 건초 더미가 하나도 없어도 된다. 다만 건초 더미 위에는 착지하지 못한다. 베시는 여전히 게으르고 싶어서 북서쪽 모서리에서 남동쪽 모서리까지 가는 데 필요한 최소 점프 횟수를 알고 싶어 한다.

입력은 테스트 케이스 하나로 이루어진다. 첫째 줄에 정수 $n$과 $k$가 주어진다 ($1 \le n, k \le 2000$). $n$은 정사각 격자의 한 변 길이이고, $k$는 베시가 한 번에 뛸 수 있는 최대 칸 수다. 다음 $n$개 줄에는 길이가 정확히 $n$인 문자열이 한 줄씩 주어진다. 문자열에는 건초 더미를 뜻하는 '#'와 빈 칸을 뜻하는 '.'만 나온다. 격자의 북서쪽 모서리 칸과 남동쪽 모서리 칸은 항상 비어 있다.

베시가 북서쪽 모서리에서 남동쪽 모서리까지 가는 데 필요한 최소 점프 횟수를 한 줄에 출력한다. 도달할 수 없으면 $-1$을 출력한다.