题目分析：
重新定义矩阵运算，$*$等价于$+$，$+$等价于$max$。
然后倍增一下，再二分一下。
代码：
#include<bits/stdc++.h>
using namespace std; int n;long long m;
struct mat{long long arr[][];}G,mmp;
mat hh[]; mat operator*(mat alpha,mat beta){
int flag = ;
for(int i=;i<=n;i++) for(int j=;j<=n;j++) if(alpha.arr[i][j]!=)flag=;
if(flag == ) return beta;
memset(mmp.arr,,sizeof(mmp.arr));
for(int k=;k<=n;k++){
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
if(alpha.arr[i][k] == || beta.arr[k][j] == ) continue;
mmp.arr[i][j]=
max(mmp.arr[i][j],alpha.arr[i][k]+beta.arr[k][j]);
}
}
}
return mmp;
} mat res;
long long fstpow(long long pw){
hh[] = G;pw *= ;
int bit = ;
while((1ll<<bit) <= pw){
hh[bit+] = hh[bit]*hh[bit];bit++;
int flag = ;
for(int i=;i<=n;i++) if(hh[bit].arr[][i] >= m) flag = ;
if(flag) break;
}
return bit;
} void read(){
scanf("%d%lld",&n,&m);
for(int i=;i<=n;i++) for(int j=;j<=n;j++) scanf("%lld",&G.arr[i][j]);
} void work(){
int z = fstpow(m);
for(int i=;i<=n;i++) for(int j=;j<=n;j++) res.arr[i][j] = ;
long long ans = (1ll<<z);
long long now = ;
while((--z) >= ){
mat maye = res*hh[z];int flag = ;
for(int i=;i<=n;i++) if(maye.arr[][i] >= m){flag = ;break;}
if(flag) ans = now+(1ll<<z);
else now += (1ll<<z),res = maye;
}
printf("%lld\n",ans);
} int main(){
int Tmp; scanf("%d",&Tmp);
while(Tmp--){
read();
work();
}
return ;
}