#include <stdio.h>#include <string>#include <string.h>#include <iostream>#include <cmath>#include <cstdlib>#include <math.h>#include <stdlib.h>#include <algorithm>#include <queue>#include <stack>#include <set>#include <map>#include <sstream>using namespace std;#define LL long longstruct Matr{LL a[105][105];};LL n, L;Matr matr_mult(Matr a, Matr b){Matr ans;for(LL i = 0; i < n; i++){for(LL j = 0; j < n; j++){ans.a[i][j] = -999999999;for(LL k = 0; k < n; k++){if(ans.a[i][j] < a.a[i][k] + b.a[k][j])ans.a[i][j] = a.a[i][k] + b.a[k][j];}}}return ans;}Matr mult(Matr a, LL k){Matr ans;memset(ans.a, 0, sizeof(ans.a));while(k){if(k & 1)ans = matr_mult(ans, a);k = k / 2;a = matr_mult(a, a);}return ans;}int main(){LL t;scanf("%lld", &t);while(t--){scanf("%lld%lld", &n, &L);Matr ans;for(LL i = 0; i < n; i++){for(LL j = 0; j < n; j++)scanf("%lld", &ans.a[i][j]);}ans = mult(ans, L - 1);LL res = -999999999;for(LL i = 0; i < n; i++){for(LL j = 0; j < n; j++){res = max(ans.a[i][j], res);}}printf("%lldn", res);}}
