你现在正在驾驶一架 UFO，在一个由点 $(x, y)$ 组成的 $n \times n$ 网格中飞行，其中 $1 \le x, y \le n$。有些点是不可通行的（用 * 表示），其他点是可通行的（用 . 表示）。

最初，你位于点 $(1, 1)$，你的目标是尽可能快地到达 $(n, n)$。当你位于点 $(x, y)$ 时，你可以在一秒钟内传送至 $(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