该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

现有无穷多块大奶酪竖直摞在一起，从下至上依次编号为 0, 1, 2, ……

每块大奶酪中间有 N 个半径相同的球形空洞，依次编号为 1 ~ N。同一块奶酪中的空洞都是相离的，即无法从一个空洞到达另一个空洞。

现在，有一只小老鼠 Jerry 正处于编号为 0 的奶酪中的第 1 个空洞中，它想要跑到第 M 块奶酪或者更高的奶酪中。

要想从下方的奶酪空洞到达上方的奶酪空洞中，需要借助一些单向隧道。隧道用三个整数 x, y, z 描述，表示对于任意一块奶酪 i，有一条从该奶酪的第 x 个空洞通往奶酪 i+z 的第 y 个空洞的单向隧道。不存在从上方奶酪到达下方奶酪的隧道。

怕黑的 Jerry 很不喜欢走隧道。他想知道，他至少需要通过多少条隧道才能跑到第 M 块奶酪或者更高的奶酪中?

你能帮助他吗？

输入格式

多组数据。

第一行，包含一个正整数 $T$，代表该输入文件中所含的数据组数。

接下来是 $T$ 组数据，每组数据的格式如下：

第一行包含两个正整数 $N, M$，两个数之间以一个空格分开，分别代表每块奶酪中空洞的数量，Jerry 的最低目标奶酪编号。

接下来的 $N$ 行，每行包含 $N$ 个整数，组成一个 N×N 的矩阵 A。 如果矩阵的第 x 行第 y 列的元素 $A_{x,y} > 0$，则表示有隧道 $(x,y,A_{x,y})$。

输出格式

$T$ 行，每行一个整数，分别对应 $T$ 组数据的答案。如果对于某组数据，Jerry 无法完成目标，则对应答案输出 -1

样例输入

3
5 66
0 1 0 50 0
0 0 2 0 0
10 0 0 0 0
0 0 0 0 1
0 0 0 5 2
5 80
0 1 0 50 0
0 0 2 0 0
10 0 0 0 0
0 0 0 0 1
0 0 0 5 2
5 80
0 1 0 50 0
0 0 2 0 0
0 0 0 0 0
0 0 0 0 1
0 0 0 0 0

样例输出

6
9
-1

数据范围

共 10 个测试点，全部满足：T = 5，1 ≤ N ≤ 100，1 ≤ m ≤ $10^{18}$，0 ≤ $A_{x,y}$ ≤ $10^{18}$。其中：

有 1 个测试点：N = 2；

另有 2 个测试点：M ≤ 3000；

另有 2 个测试点：要么 $A_{x,y}$=0，要么 $A_{x,y}$ ≥ $10^{15}$；

另有 3 个测试点：N = 40。