#include <bits/stdc++.h>
#define N 200005
#pragma GCC optimize(3, "Ofast", "inline")
#define mod 998244353
using i64 = long long;
using namespace std;

int vis[N], pri[N], tot, mu[N];
vector<int> fac[N], num[N];

int n, m, l;
vector<int> adj[N], T[N];
int dfn[N], low[N], dfstot, cnt;
stack<int> sta;

i64 path[N], f[N], g[N];

void tarjan(int cur)
{
    dfn[cur] = low[cur] = ++dfstot;
    sta.push(cur);
    for (int i : adj[cur])
    {
        if (!dfn[i])
        {
            tarjan(i);
            low[cur] = min(low[cur], low[i]);
            if (low[i] == dfn[cur])
            {
                cnt++;
                int node;
                do
                {
                    node = sta.top();
                    sta.pop();
                    T[cnt].push_back(node);
                    T[node].push_back(cnt);
                } while (node != i);
                T[cur].push_back(cnt);
                T[cnt].push_back(cur);
            }
        }
        else
            low[cur] = min(low[cur], dfn[i]);
    }
}
void dfs(int cur, int fa, int fac)
{
    for (int i : T[cur])
    {
        if (i == fa)
            continue;
        dfs(i, cur, fac);
    }
    if (cur <= n)
        path[cur] = 1;
    else
        path[cur] = 0;
    for (int i : T[cur])
    {
        if (i == fa)
            continue;
        if (cur <= n || T[cur].size() > 2)
            g[fac] = (g[fac] + (i64)path[cur] * path[i] % mod) % mod;
        if (cur > n && T[cur].size() > 2)
            path[cur] = (path[cur] + 2 * path[i] % mod) % mod;
        else
            path[cur] = (path[cur] + path[i]) % mod;
    }
}
void solve()
{
    cin >> n >> m >> l;
    vector<array<int, 3>> e(m);
    for (int i = 0; i < m; i++)
    {
        cin >> e[i][0] >> e[i][1] >> e[i][2];
        for (int j : fac[e[i][2]])
            num[j].push_back(i);
    }
    for (int d = 1; d <= l; d++)
    {
        for (int i : num[d])
        {
            adj[e[i][0]].push_back(e[i][1]);
            adj[e[i][1]].push_back(e[i][0]);
        }
        cnt = n;
        for (int i : num[d])
        {
            if (!dfn[e[i][0]])
            {
                tarjan(e[i][0]);
                dfs(e[i][0], 0, d);
            }
        }
        dfstot = 0;
        for (int i = n + 1; i <= cnt; i++)
            T[i].clear();
        while (!sta.empty())
            sta.pop();
        for (int i : num[d])
        {
            T[e[i][0]].clear();
            T[e[i][1]].clear();
            adj[e[i][0]].clear();
            adj[e[i][1]].clear();
            dfn[e[i][0]] = low[e[i][0]] = 0;
            dfn[e[i][1]] = low[e[i][1]] = 0;
        }
    }
    for (int i = 1; i <= l; i++)
        for (int j = i; j <= l; j += i)
            f[i] = (f[i] + (g[j] * mu[j / i] + mod) % mod) % mod;
    for (int i = 2; i <= l; i++)
        f[i] ^= f[i - 1];
    cout << f[l] << '\n';
    fill(f + 1, f + l + 1, 0);
    fill(g + 1, g + l + 1, 0);
    for (int i = 1; i <= l; i++)
        num[i].clear();
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    mu[1] = 1;
    for (int i = 2; i <= 1e5; i++)
    {
        if (!vis[i])
            pri[++tot] = i, mu[i] = -1;
        for (int j = 1; j <= tot && i * pri[j] <= 1e5; j++)
        {
            vis[i * pri[j]] = 1;
            if (i % pri[j] == 0)
                break;
            mu[i * pri[j]] = -mu[i];
        }
    }
    for (int i = 1; i <= 1e5; i++)
        for (int j = i; j <= 1e5; j += i)
            fac[j].push_back(i);
    int t = 1;
    cin >> t;
    while (t--)
        solve();
}