Description

恶魔猎手成功拿到了古尔丹之颅，吸收了古尔丹之颅的力量后，恶魔猎手全身变的一片漆黑，后背上也长出了一对翅膀，也就是说：他会飞了！！
  兴奋一阵子后，他发现了他的困境，他出不去了！！
  因为在路上他消耗了太多的生命值，吸收古尔丹之颅又花费了他很大力气，他发现他现在非常虚弱，不能再承受任何伤害了。但他又欣喜的发现，吸收了古尔丹之颅的力量后他的身体变的异常强化，一般的小怪不能再对他造成任何伤害了，而且他能飞了，在空中他不会受到任何伤害，但是他发现他的翅膀非常奇怪，每次一定要飞行k距离才能停下来，两点间(x1,y1)(x2,y2)的距离定义为|x1-x2|+|y1-y2|。为了更好的熟悉他的新翅膀，他决定完全靠飞出去而不去步行。
  问恶魔猎手在不受到任何伤害的情况下最少需要飞行几次，才能到达出口（1，1），他现在处于（n，n）位置。

Input

输入有多组数据。
每组由n+1行构成。
第一行两个数n(1<=n<=500)，k(1<=k<=n)；
第二行到第n+1行，是一个n行n列的01矩阵，0代表在该点恶魔猎手不会受到伤害，1代表会受到伤害。

Output

输出恶魔猎手在不受到任何伤害的情况下最少需要飞行几次，才能到达出口。如果不能到达出口，输出-1；

Sample Input

5 2
0 1 0 1 0
1 0 1 0 1
0 1 1 1 0
1 0 1 0 1
1 1 0 1 0
5 2
1 0 1 1 1
1 1 0 1 1
1 0 1 0 0
1 0 0 0 0
0 0 0 0 0

Sample Output

4
-1

HINT

Source

NBU OJ