#include<bits/stdc++.h>
#define ll long long
#define GC getchar()
#define N 1000010
#define P 998244353
#define PC putchar
using namespace std;
ll re(){
	ll s=0,b=1; char c=GC;
	while(c>'9'||c<'0'){if(c=='-')b=-b; c=GC;}
	while(c<='9'&&c>='0'){s=(s<<1)+(s<<3)+(c^48); c=GC;}
	return s*b;
}
void ks(ll s){
	if(s>=10)ks(s/10); PC((s%10)|48);
}
ll ksm(ll ds,ll zs){
	ll s=1;
	while(zs){
		if(zs&1)s=s*ds%P; zs>>=1; ds=ds*ds%P;
	} return s;
}
int n,m,L,x,y,z,he[N],tt,zh[N],zd,fd,fdz[N],zh2[N],zd2;
int tu,hf[N],dl[N],t,o;
ll s[N],an[N],eny=ksm(2,P-2);
vector<int>gcb[N];
vector<int>dj[N];
vector<int>ox[N],oy[N],ofd[N]; 
vector<int>ys[N];
bool vi[N];
struct A{int ne,to,z,yz;}b[N<<1];
struct B{int x,y,z,bl;}yb[N];
struct C{int ne,to;}rb[N<<1];
int gcd(int x,int y){return y?gcd(y,x%y):x;}
void dfs(int x,int f){
	zh2[++zd2]=x; vi[x]=1;
	for(int i=he[x]; i; i=b[i].ne){
		int v=b[i].to; if(v==f)continue;
		if(vi[v]){
			fd++; gcb[fd].push_back(b[i].yz);
			yb[b[i].yz].bl=fd; fdz[fd]=b[i].z;
			for(int j=zd; j>=1; --j){
				yb[zh[j]].bl=fd; gcb[fd].push_back(zh[j]);
				fdz[fd]=gcd(fdz[fd],yb[zh[j]].z);
				if(yb[zh[j]].x==v||yb[zh[j]].y==v)break;
			}
			for(int j=zd2; j>=1; --j){
				dj[fd].push_back(zh2[j]);
				if(zh2[j]==v)break;
			}
		} else{
			zh[++zd]=b[i].yz;
			dfs(v,x); zd--;
		}
	}
	zd2--;
}
void add(int x,int y){
	rb[++tu].to=y; rb[tu].ne=hf[x]; hf[x]=tu;
	rb[++tu].to=x; rb[tu].ne=hf[y]; hf[y]=tu;
	if(vi[x]){vi[x]=0; dl[++t]=x;}
	if(vi[y]){vi[y]=0; dl[++t]=y;}
}
void jfd(int x){
	for(int i=0; i<dj[x].size(); ++i)add(x+n,dj[x][i]);
}
void p_dfs(int x,int f){
	s[x]=0; vi[x]=1;
	for(int i=hf[x]; i; i=rb[i].ne){
		int v=rb[i].to; if(v==f)continue;
		p_dfs(v,x); s[x]=(s[x]+s[v])%P;
	}
	if(x<=n)s[x]=(s[x]+1)%P;
	 else s[x]=s[x]*2%P;
}
void dft(int x,int f){
	if(x<=n)an[o]=(an[o]+s[x]-1+P)%P;
	for(int i=hf[x]; i; i=rb[i].ne){
		int v=rb[i].to; if(v==f)continue;
		s[x]=(s[x]-s[v]+P)%P; if(x>n)s[x]=(s[x]-s[v])%P;
		s[v]=(s[v]+s[x])%P; if(v>n)s[v]=(s[v]+s[x])%P;
		dft(v,x);
		s[v]=(s[v]-s[x]+P)%P; if(v>n)s[v]=(s[v]-s[x]+P)%P;
		s[x]+=s[v]; if(x>n)s[x]+=s[v]; s[x]%=P;
	}
}
void wo(){
	for(int i=1; i<=n+fd; ++i)vi[i]=he[i]=0;
	for(int i=1; i<=L; ++i)an[i]=0,ox[i].clear(),oy[i].clear(),ofd[i].clear();
	for(int i=0; i<=fd; ++i)gcb[i].clear(),dj[i].clear();
	tt=0; fd=0;
	
	n=re(); m=re(); L=re();
	for(int i=1; i<=m; ++i){
		x=re(),y=re(); z=re(); yb[i].x=x; yb[i].y=y; yb[i].z=z; yb[i].bl=0;
		b[++tt].to=y; b[tt].ne=he[x]; he[x]=tt; b[tt].z=z; b[tt].yz=i;
		b[++tt].to=x; b[tt].ne=he[y]; he[y]=tt; b[tt].z=z; b[tt].yz=i;
	}
	for(int i=1; i<=n; ++i)	if(!vi[i])dfs(i,0);
	for(int i=n+1; i<=n+fd; ++i)vi[i]=1;
	for(int i=1; i<=m; ++i)
	 if(!yb[i].bl)gcb[0].push_back(i);
	for(int i=0; i<gcb[0].size(); ++i){
		for(int j=0; j<ys[yb[gcb[0][i]].z].size(); ++j){
			ox[ys[yb[gcb[0][i]].z][j]].push_back(yb[gcb[0][i]].x);
			oy[ys[yb[gcb[0][i]].z][j]].push_back(yb[gcb[0][i]].y);
		}
	}
	for(int i=1; i<=fd; ++i){
		for(int j=0; j<ys[fdz[i]].size(); ++j)
		 ofd[ys[fdz[i]][j]].push_back(i);
		for(int j=0; j<gcb[i].size(); ++j)
		 for(int k=0; k<ys[yb[gcb[i][j]].z].size(); ++k) 
		  if(fdz[i]%ys[yb[gcb[i][j]].z][k]!=0){
		  	ox[ys[yb[gcb[i][j]].z][k]].push_back(yb[gcb[i][j]].x);
			oy[ys[yb[gcb[i][j]].z][k]].push_back(yb[gcb[i][j]].y);
		  }
	}
	for(o=1; o<=L; ++o){
		for(int i=0; i<ox[o].size(); ++i)add(ox[o][i],oy[o][i]);
		for(int i=0; i<ofd[o].size(); ++i)jfd(ofd[o][i]);
		for(int i=1; i<=t; ++i)
		 if(!vi[dl[i]]){p_dfs(dl[i],0); dft(dl[i],0);}
		for(int i=1; i<=t; ++i)hf[dl[i]]=0; tu=0; t=0;
	}
	for(int i=1; i<=L; ++i)an[i]=an[i]*eny%P;
	for(int i=L; i>=1; --i)
	 for(int j=i+i; j<=L; j+=i)an[i]=(an[i]-an[j]+P)%P;
	ll ans=0; for(int i=1; i<=L; ++i)ans^=an[i]; ks(ans); PC('\n'); 
}
int main(){
	for(int i=1; i<=100000; ++i)
	 for(int j=i; j<=100000; j+=i)ys[j].push_back(i);
	int T=re();
	while(T--)wo();
}