#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
int n,m;
int dis[405][405],ok[405][405],dd[405][405];
int pre[500005],suf[500005];
int h[405],h1[405];//总方案数，总方案数的权值和
int g[405],g1[405];//不成立的方案数，不成立的方案数的权值和。
int f[405],f1[405];
//每次转移考虑枚举 1 所在的连通块大小
int inv[500005],jie[500005];
int s1[505],s2[505],s3[505];//不带m的方案数和随便的方案数和必须带m的方案数
int q1[500005],q2[500005],q3[500005];int tot = 0;
int qp(int p,int q){
	int ans = 1,pro = p%mod;
	while(q){
		if(q&1)ans = ans*(pro)%mod;
		pro = pro*pro%mod;q>>=1;
	}return ans;
}int C(int n,int m){
	if(m>n)return 0;
	return jie[n]*inv[m]%mod*inv[n-m]%mod;
}int pw[200005];
void init(){
	memset(s1,0,sizeof(s1));memset(s2,0,sizeof(s2));memset(f,0,sizeof(f));memset(f1,0,sizeof(f1));
	pw[0] = 1;for(int i = 1;i<=n*n;i++)pw[i] =pw[i-1]*(m)%mod;
	for(int i = 1;i<=n;i++){
		h[i] = qp(2,i*(i-1)/2);h1[i] = qp(m+1,i*(i-1)/2);
		//for(int j =0;j<=i*(i-1)/2;j++){
		//	h1[i] = (h1[i]+pw[j]*C(i*(i-1)/2,j))%mod;
		//}
	}f[1] = 1,f1[1] = 1,g[1] = 0,g1[1]=  0;
	for(int i = 2;i<=n;i++){g[i] = g1[i] = 0;
		for(int k = 1;k<i;k++){
			g[i] += C(i-1,k-1)*f[k]%mod*h[i-k]%mod;
			g1[i] += C(i-1,k-1)*f1[k]%mod*h1[i-k]%mod*pw[k*(i-k)]%mod;
			g[i]%=mod,g1[i]%=mod;
		}f[i] = (h[i]-g[i]+mod)%mod,f1[i] = (h1[i]-g1[i]+mod)%mod;
	}//牛魔，怎么记录的方案数没有用啊。没事就放在那里吧。
	for(int i = 1;i<=n;i++)s2[i] =  f1[i],s3[i] = f1[i];
	pw[0] = 1;for(int i = 1;i<=n*n;i++)pw[i] =pw[i-1]*(m-1)%mod;
	for(int i = 1;i<=n;i++){
		h[i] = qp(2,i*(i-1)/2);h1[i] = qp(m,i*(i-1)/2);
	}f[1] = 1,f1[1] = 1,g[1] = 0,g1[1]=  0;
	for(int i = 2;i<=n;i++){g[i] = g1[i] = 0;
		for(int k = 1;k<i;k++){
			g[i] += C(i-1,k-1)*f[k]%mod*h[i-k]%mod;
			g1[i] += C(i-1,k-1)*f1[k]%mod*h1[i-k]%mod*pw[k*(i-k)]%mod;
			g[i]%=mod,g1[i]%=mod;
		}f[i] = (h[i]-g[i]+mod)%mod,f1[i] = (h1[i]-g1[i]+mod)%mod;
	}for(int i = 1;i<=n;i++)s1[i] = f1[i],s3[i] = (s3[i]-f1[i]+mod)%mod;
}
vector<int>p[405];int col[405],sz[405],nw;
void dfs(int now){col[now] = nw;
	for(int i =0;i<p[now].size();i++){
		if(!col[p[now][i]])dfs(p[now][i]);
	}
}
void solve(int id){
		cin >> n >> m;nw = 0;init();
		for(int i = 1;i<=n;i++)sz[i] = col[i] = 0;
		for(int i = 1;i<=n;i++)p[i].clear();

		for(int i = 1;i<=n;i++){
			for(int j = 1;j<=n;j++){
				cin >> dis[i][j];
				if(dis[i][j] == 0){
					p[i].push_back(j),p[j].push_back(i);
				}
			}
		}//if(id == 42){
		//	cout << n << " " << m << '\n';
		//	for(int i = 1;i<=n;i++){
		//	for(int j = 1;j<=n;j++){
		//		cout << dis[i][j] << " ";
		//	}cout << '\n';
		//}}return;
		for(int i = 1;i<=n;i++)for(int j =1;j<=n;j++){
			if(dis[i][j]>m){
				cout << 0 << endl;return;
			}if(dis[i][j]!=dis[j][i]){
				cout << 0 << endl;return;
			}
		}
		for(int i = 1;i<=n;i++)if(!col[i])nw++,dfs(i);
		for(int i = 1;i<=nw;i++){
			vector<int>pp;
			for(int j =1;j<=n;j++)if(col[j] == i)pp.push_back(i);int ok = 1;
			sz[i] = pp.size();
			for(int i = 1;i<pp.size();i++){
				for(int j = 1;j<=n;j++){
					if(dis[pp[i]][j]!=dis[pp[0]][j]){ok =0;break;}
				}
			}if(!ok){
				cout << 0 << endl;return;
			}
		}for(int i = 1;i<=n;i++){
			for(int j = 1;j<=n;j++){
				dd[col[i]][col[j]] = dis[i][j];
			}
		}memcpy(dis,dd,sizeof(dd));n = nw;
		for(int i = 1;i<=n;i++)for(int j = 1;j<=n;j++)ok[i][j] =0;
		for(int i = 1;i<=n;i++){
			for(int j = 1;j<=n;j++){
				if(i == j)continue;
				for(int k = 1;k<=n;k++){
					if(k == i or k == j)continue;
					if(dis[i][j] == dis[i][k]+dis[k][j]){
				//		cout << i << " " << j << " " << k << " " << dis[i][k]+dis[k][j] << endl;
						ok[i][j] = 1;break;
					}if(dis[i][j]>dis[i][k]+dis[k][j]){
						cout << 0 << endl;return;
					}
				}
			}
		}
	int okk = 0;tot =0 ;
	for(int i = 1;i<=n;i++){
		q1[++tot] = s1[sz[i]],q2[tot] = s2[sz[i]],q3[tot] = s3[sz[i]];
	}
	for(int i= 1;i<=n;i++){
		for(int j = i+1;j<=n;j++){
			if(!ok[i][j]){
				int tt = sz[i]*sz[j],ans = 0;
				for(int k = 1;k<=tt;k++){
					//枚举第一个等于最小值的位置
					ans+=qp(m-dis[i][j],k-1)*qp(m-dis[i][j]+1,tt-k)%mod;ans%=mod;
				}q2[++tot] = ans;ans =0 ;
				for(int k = 1;k<=tt;k++){
					ans+=qp(m-dis[i][j]-1,k-1)*qp(m-dis[i][j],tt-k)%mod;ans%=mod;
				}q1[tot] = ans;q3[tot] = (q2[tot]-q1[tot]+mod)%mod;
			}else{
				int tt = sz[i]*sz[j],ans =0 ;
				q2[++tot] = qp(m-dis[i][j]+1,tt);q1[tot] = qp(m-dis[i][j],tt);
				q3[tot] = (q2[tot]-q1[tot]+mod)%mod;
			}
			if(!ok[i][j] and dis[i][j] == m){
				okk = 1;
			}
		}
	}if(okk == 1){
		int ans = 1;
		for(int i = 1;i<=tot;i++)ans = ans*q2[i]%mod;
		cout << ans << endl;
	}else{
		pre[0] = suf[tot+1] = 1;
	//	for(int i = 1;i<=tot;i++)cout << " " << q1[i] << " " << q2[i] << " " << q3[i] << endl;
		for(int i = 1;i<=tot;i++)pre[i] = pre[i-1]*q1[i]%mod;
		for(int i = tot;i>=1;i--)suf[i] = suf[i+1]*q2[i]%mod;
		int ans = 0;
		for(int i = 1;i<=tot;i++)ans += pre[i-1]*q3[i]%mod*suf[i+1]%mod,ans%=mod;
		cout << ans << endl;
	}
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);;
	jie[0] = inv[0] = 1;for(int i= 1;i<=500000;i++)jie[i] = jie[i-1]*i%mod,inv[i] = qp(jie[i],mod-2);
	int t;cin >> t;
	for(int i =1;i<=t;i++){
		solve(i);
	}

	return 0;
}
/*
回来吧刺激小院闲窗春色深
历历在目的小院闲窗春色深，重帘未卷影沉沉莫名在流淌。
依稀记得倚楼无语理瑶琴，还有给力的远岫出云催薄暮。
把细风吹雨弄轻阴都给打退，就算梨花欲谢恐难禁也不累。
感觉硬贴进来不是很应景。

直接考虑有哪些边是在某个最短路里的，然后这些边权就确定了，其他的任意
然后我们直接钦定最早的m在哪里。

牛魔，咋还有0的情况。
真牛魔难。
首先把距离为0的缩点，中间判无解
然后考虑距离为0的连通块内部有多少种连边方式
dp，参考带标号无向连通图计数，加上权值
处理最大值为m只需要单步容斥。
1
4 2
0 1 1 2
1 0 1 1
2 1 0 2
2 1 2 0


*/