#include "iostream"
#include "cstring"
#include "cstdio"
#include "algorithm"
#include "queue"
#include "vector"
#include "queue"
#include "stack"
#include "ctime"
#include "set"
#include "map"
using namespace std;
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define mp make_pair
#define rep( i , a , b ) for( int i = (a) , i##end = b ; i <= i##end ; ++ i )
#define per( i , a , b ) for( int i = (a) , i##end = b ; i >= i##end ; -- i )
#define mem( a ) memset( a , 0 , sizeof (a) )
#define all( x ) x.begin() , x.end()
//#define int long long
typedef long long ll;
const int P = 998244353;
const int MAXN = 2e5 + 10;
int n , m , L;

int pri[MAXN] , mu[MAXN] , en;
void sieve() {
	mu[1] = 1;
	for( int i = 2 ; i < MAXN ; ++ i ) {
		if( !pri[i] ) pri[++ en] = i , mu[i] = -1;
		for( int j = 1 ; j <= en && pri[j] * i < MAXN ; ++ j ) {
			pri[i * pri[j]] = 1;
			if( i % pri[j] == 0 ) {
				mu[i * pri[j]] = 0;
				break;
			}
			mu[i * pri[j]] = -mu[i];
		}
	}
}

vector<pii> ed[MAXN];

vi G[MAXN];

int cnt; vi g[MAXN];
int dfn[MAXN] , low[MAXN] , clo;
int stk[MAXN] , tp;

void tarjan( int u ) {
	dfn[u] = low[u] = ++ clo;
	stk[++ tp] = u;
	for( int v : G[u] ) {
		if( !dfn[v] ) {
			tarjan( v );
			low[u] = min( low[u] , low[v] );
			if( low[v] == dfn[u] ) {
				++ cnt;
				g[u].pb( cnt );
//					cout << "--->   " << u << ' ' << cnt << endl;
				int x;
				do {
					x = stk[tp];
					g[cnt].pb( x );
//					cout << "--->   " << cnt << ' ' << x << endl;
					-- tp;
				} while( x != v );
			}
		} else low[u] = min( low[u] , dfn[v] );
	}
}

int cnd[MAXN] , as;
void dfs( int u ) {
	int cn = ( u <= n ) , re = 0;
	for( int v : g[u] ) {
		dfs( v );
		re = ( re + cn * 1ll * cnd[v] ) % P;
		cn = ( cn + cnd[v] ) % P;
	}
	if( u > n && g[u].size() > 1 ) as = ( as + re * 2ll ) % P , cnd[u] = cn * 2ll % P;
	else as = ( as + re ) % P , cnd[u] = cn;
}

int re[MAXN] , res[MAXN];

void solve() {
	cin >> n >> m >> L;
	rep( i , 1 , m ) {
		int u , v , w;
		scanf("%d%d%d",&u,&v,&w);
		ed[w].eb( u , v );
	}
	rep( k , 1 , L ) {
		vi nd;
		for( int t = k ; t <= L ; t += k ) 
			for( auto& e : ed[t] ) 
				G[e.fi].pb( e.se ) , G[e.se].pb( e.fi ) , nd.pb( e.fi ) , nd.pb( e.se );
		cnt = n , tp = 0 , clo = 0;
		vi rt;
		for( int x : nd ) if( !dfn[x] ) tarjan( x ) , rt.pb( x );
		as = 0;
		for( int x : rt ) {
			dfs( x );
		}
		re[k] = as;
		
		for( int x : nd ) G[x].clear() , dfn[x] = low[x] = 0 , g[x].clear() , cnd[x] = 0;
		rep( i , n + 1 , cnt ) g[i].clear() , dfn[i] = low[i] = 0 , cnd[i] = 0;
	}
	
	for( int k = 1 ; k <= L ; ++ k ) for( int t = 1 ; t * k <= L ; ++ t )
		res[k] = ( res[k] * 1ll + P + mu[t] * re[k * t] ) % P;
		
	int ans = 0;
	rep( i , 1 , L ) {
		ans ^= res[i];
//		printf("%d: %d %d\n",i,re[i],res[i]);
	}
	printf("%d\n",ans);
	
	rep( i , 1 , L ) ed[i].clear() , res[i] = re[i] = 0;
}

signed main() {
	sieve();
//	freopen("in","r",stdin);
//	freopen("out","w",stdout);
	int T;cin >> T;while( T-- ) solve();
//	solve();
}