Description：

一幢无穷高的大楼上有 $N$ 部电梯，一部电梯可以从任意一层 $i$ 的 $u$ 房间到第 $i+w$ 层的 $v$ 房间，问最少乘几次电梯可以到达 $\ge m$ 层。

$T\le 5$ $N\le 100$

Solution：

二分走几步， $floyed+$ 矩阵快速幂求最长路判断是否有 $f[1][k]\ge m$ ，但是会超时，用倍增找出来最小的能到达 $m$ 层及以上的 $f^k$ ，再倍增即可。倍增时要保证始终不能到 $m$ ，最后还要手动加一。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long ll;

ll n,m;

int testcases;

#define MAXN 101

#define INF 0x3f3f3f3f3f3f3f3f

ll read()

{

	register ll res = 0;

	char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

struct matrix

{

	ll d[MAXN][MAXN];

	matrix(){memset(d,0,sizeof(d));}

	ll *operator [](int x){return d[x];}

	friend matrix operator * (matrix a,matrix b)

	{

		matrix c;

		for(int i = 1;i <= n;++i)

		{

			for(int j = 1;j <= n;++j)

			{

				c[i][j] = -INF;

				for(int k = 1;k <= n;++k)

				{

					c[i][j] = max(c[i][j],a[i][k] + b[k][j]);

				}

			}

		}

		return c;

	}

}f[MAXN];

bool check(matrix k)

{

	for(int i = 1;i <= n;++i)

	{

		if(k[1][i] >= m)return true;

	}

	return false;

}

void work()

{

	n = read();m = read();

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= n;++j)

		{

			f[0][i][j] = read();

			if(f[0][i][j] == 0 && i != j)f[0][i][j] = -INF;

		}

	}

	int cnt = 0;

	while(true)

	{

		f[cnt + 1] = f[cnt] * f[cnt];

		if(check(f[++cnt]))break; 

	}

	matrix res = f[0];

	ll ans = 1;

	for(int i = cnt;i >= 0;--i)

	{

		if(!check(res * f[i]))

		{

			res = res * f[i];

			ans += (1ll << i);

		}

	}

	cout << ans + 1 << endl; 

	return;

}

int main()

{

	scanf("%d",&testcases);

	for(int i = 1;i <= testcases;++i)

	{

		work();

	}

	return 0;

}