#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=2e5+5;
const int maxv=1e5+5;
int n,m,L;
struct edge
{
    int u,v,w;
}e[maxn];
int pr[maxv],cnt,mu[maxn];
bool vis[maxv];
vector <int> fac[maxv],q[maxn];
void init()
{
    mu[1]=1;
    for(int i=2;i<maxv;i++)
    {
        if(!vis[i]) pr[++cnt]=i,mu[i]=-1;
        for(int j=1;j<=cnt && 1ll*i*pr[j]<maxv;j++)
        {
            vis[i*pr[j]]=1;
            if(i%pr[j]==0){mu[i*pr[j]]=0; break;}
            else mu[i*pr[j]]=-mu[i];
        }
    }
    for(int i=1;i<maxv;i++)
        for(int j=i;j<maxv;j+=i)
            fac[j].push_back(i);
}
ll ans[maxn];
vector <int> G[maxn],GG[maxn<<1];
int dfn[maxn],low[maxn],dfstime;
int tot,st[maxn],top;
ll d[maxn];
void tarjan(int u,int fa)
{
    dfn[u]=low[u]=++dfstime;
    d[u]=0; st[++top]=u;
    for(int to:G[u])
    {
        if(!dfn[to])
        {
            tarjan(to,u);
            low[u]=min(low[u],low[to]);
            d[u]+=d[to];
            if(low[to]==dfn[u]) // bridge edge
            {
                ++tot;
                GG[tot].clear();
                int v=st[top];
                while(v!=to)
                {
                    GG[tot].push_back(v);
                    GG[v].push_back(tot);
                    top--; v=st[top];
                }
                top--; GG[tot].push_back(to);
                GG[to].push_back(tot);
                GG[tot].push_back(u);
                GG[u].push_back(tot);
            }
        }
        else
        {
            low[u]=min(low[u],dfn[to]);
            if(to!=fa) d[u]++,d[to]--;
        }
    }
}
ll f[maxn<<1];
void add(ll &x,ll y)
{
    x=(x+y)%mod;
}
void calc(int u,int fa,int id)
{
    for(int to:GG[u])
    {
        if(to==fa) continue;
        calc(to,u,id);
    }
    if(u<=n)
    {
        f[u]=1;
        for(int to:GG[u])
        {
            if(to==fa) continue;
            add(ans[id],f[u]*f[to]%mod);
            add(f[u],f[to]);
        }
    }
    else if(GG[u].size()==2)
    {
        f[u]=0;
        for(int to:GG[u])
        {
            if(to==fa) continue;
            add(f[u],f[to]);
        }
    }
    else
    {
        f[u]=0;
        for(int to:GG[u])
        {
            if(to==fa) continue;
            add(ans[id],f[u]*f[to]%mod);
            add(f[u],2ll*f[to]%mod);
        }
    }
}
int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    int T; scanf("%d",&T);
    init();
    while(T--)
    {
        scanf("%d%d%d",&n,&m,&L);
        int x,y,z;
        for(int i=1;i<=L;i++) ans[i]=0,q[i].clear();
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
            for(int j:fac[e[i].w]) q[j].push_back(i);
        }
        vector <int> p;
        for(int i=1;i<=L;i++)
        {
            p.clear();
            for(int id:q[i])
            {
                int u=e[id].u,v=e[id].v;
                G[u].clear(); G[v].clear();
                GG[u].clear(); GG[v].clear();
                dfn[u]=dfn[v]=0; p.push_back(u); p.push_back(v);
            }    
            for(int id:q[i])
            {
                int u=e[id].u,v=e[id].v;
                G[u].push_back(v); G[v].push_back(u);
            }
            tot=n; dfstime=top=0;
            for(int u:p)
                if(!dfn[u]) tarjan(u,0),calc(u,0,i);
            // printf("[%d]:%d %lld\n",i,tot,ans[i]);
            // for(int j=1;j<=tot;j++)
            // {
            //     printf("%d: ",j);
            //     for(int k:GG[j]) printf("%d ",k);
            //     printf("\n");
            // }
        }
        for(int i=1;i<=L;i++) 
        {
            for(int j=2;i*j<=L;j++)
                ans[i]+=1ll*mu[j]*ans[i*j];
            ans[i]=(ans[i]%mod+mod)%mod;
        }
        ll res=0;
        for(int i=1;i<=L;i++) res^=ans[i];
        printf("%lld\n",res);
    }
    return 0;
}