题目描述

xz 是一个旅游爱好者，这次他来到了一座新的城市。城市中央有一幢高耸入云的大楼。这幢楼到底有多少层呢？据说和非负整数的个数是一样多的。

xz 想爬上这座大楼来观赏新城市的全景。这幢大楼的楼层从下至上用从小到大的非负整数编号。

每层楼有 $n$ 个房间，用 $1$ 到 $n$ 的正整数编号。楼层之间用电梯连接，电梯只能上行，不能下行或者同层移动。（下楼一般自行解决）

电梯用 $(u,v,w)$ 的形式给出，表示对于任意正整数 $i$，有第 $i$ 层的房间 $u$ 到第 $i+w$ 层的房间 $v$ 有一部电梯。电梯只能从起点开往终点，不能中途停留。

xz 想要观赏城市全景，至少需要登上第 $m$ 层楼，即最终需要到达的楼层数 $\ge m$。由于乘坐电梯要缴纳高额的费用，而如果花销太大回家就没法报账了，xz 希望乘坐电梯的次数最少。现在 xz 在第 $0$ 层的 $1$ 号房间，你需要求出这个最少的乘坐次数。

输入格式

第一行包含一个正整数 $T$，表示数据的组数。

接下来的数据分为 $T$ 个部分。

每个部分第一行包含两个正整数 $n$ 和 $m$，意义见题目描述。

接下来 $n$ 行，每行包含 $n$ 个非负整数。这 $n$ 行中，第 $i$ 行第 $j$ 个数为 $w_{i,j}$，如果 $w_{i,j}$ 非零，则表示有电梯 $(i,j,w_{i,j})$。同一行各个数之间均用一个空格隔开。

输出格式

对于每组数据，输出一行一个正整数，最少的乘坐次数。

样例输入

2
6 147
0 1 0 50 0 0
0 0 1 0 0 0
20 0 0 0 0 0
0 0 0 0 1 50
0 0 0 8 0 0
0 0 0 0 0 3
6 152
0 1 0 50 0 0
0 0 1 0 0 0
20 0 0 0 0 0
0 0 0 0 1 50
0 0 0 8 0 0
0 0 0 0 0 3

样例输出

9
10

样例说明

第一组数据中，使用电梯的顺序为 $1\rightarrow 2\rightarrow 3\rightarrow 1\rightarrow 2\rightarrow 3\rightarrow 1\rightarrow 4\rightarrow 6\rightarrow 6$。

第二组数据中，使用电梯的顺序为 $1\rightarrow 2\rightarrow 3\rightarrow 1\rightarrow 2\rightarrow 3\rightarrow 1\rightarrow 4\rightarrow 5\rightarrow 4\rightarrow 6$。

第二组数据最后到达了 $153$ 层，但是没有更短的路径使得恰好到达 $152$ 层，因此答案为 $10$。

数据规模与约定

有如下几类具有特点的数据：

1. 有 $10\%$ 的数据所有的 $n=2$；
2. 有 $20\%$ 的数据 $m\leq 3000$；
3. 有 $20\%$ 的数据对于满足 $1\leq i,j\leq n$ 的整数 $i$ 和 $j$，若 $w_{i,j}\neq 0$，则有 $w_{i,j}\ge 10^{15}$；
4. 有 $30\%$ 的数据所有的 $n=40$。

以上各类数据均不包含其他类数据。

对于所有数据 $T=5$，$1\leq n\leq 100$，$1\leq m\leq 10^{18}$；对于满足 $1\leq i,j\leq n$ 的整数 $i$ 和 $j$，有 $0\leq w_{i,j}\leq 10^{18}$。数据保证能够到达 $m$ 层或更高的楼层。