#include <bits/stdc++.h>
#define N 100005
#define mod 998244353
using i64 = long long;
using namespace std;

int n, m, l, u[N << 1], v[N << 1];
vector<int> fac[N], num[N];
int pri[N], vis[N], tot, mu[N];
i64 g[N << 1], f[N << 1];

int dfn[N], low[N], dfc, cnt;
int stk[N], tp;
vector<int> adj[N], T[N << 1];

void Tarjan(int u)
{
    low[u] = dfn[u] = ++dfc; // low 初始化为当前节点 dfn
    stk[++tp] = u;           // 加入栈中
    for (int v : adj[u])
    { // 遍历 u 的相邻节点
        if (!dfn[v])
        {                                 // 如果未访问过
            Tarjan(v);                    // 递归
            low[u] = min(low[u], low[v]); // 未访问的和 low 取 min
            if (low[v] == dfn[u])
            {          // 标志着找到一个以 u 为根的点双连通分量
                ++cnt; // 增加方点个数
                // 将点双中除了 u 的点退栈，并在圆方树中连边
                for (int x = 0; x != v; --tp)
                {
                    x = stk[tp];
                    T[cnt].push_back(x);
                    T[x].push_back(cnt);
                }
                // 注意 u 自身也要连边（但不退栈）
                T[cnt].push_back(u);
                T[u].push_back(cnt);
            }
        }
        else
            low[u] = min(low[u], dfn[v]); // 已访问的和 dfn 取 min
    }
}
void dfs(int cur, int fa, int factor)
{
    for (int i : T[cur])
    {
        if (i == fa)
            continue;
        dfs(i, cur, factor);
    }
    if (cur <= n)
    {
        f[cur] = 1;
        for (int i : T[cur])
        {
            if (i == fa)
                continue;
            g[factor] = (g[factor] + (i64)f[cur] * f[i] % mod) % mod;
            f[cur] = (f[cur] + f[i]) % mod;
        }
    }
    else if (T[cur].size() <= 2)
    {
        f[cur] = 0;
        for (int i : T[cur])
        {
            if (i == fa)
                continue;
            f[cur] = (f[cur] + f[i]) % mod;
        }
    }
    else
    {
        f[cur] = 0;
        for (int i : T[cur])
        {
            if (i == fa)
                continue;
            g[factor] = (g[factor] + (i64)f[cur] * f[i] % mod) % mod;
            f[cur] = (f[cur] + 2 * f[i] % mod) % mod;
        }
    }
}

void solve()
{
    cin >> n >> m >> l;
    cnt = n;
    for (int i = 1, w; i <= m; i++)
    {
        cin >> u[i] >> v[i] >> w;
        for (int j : fac[w])
            num[j].push_back(i);
    }
    for (int d = 1; d <= l; d++)
    {
        for (int i : num[d])
            adj[u[i]].push_back(v[i]), adj[v[i]].push_back(u[i]);
        cnt = n;
        for (int i : num[d])
        {
            if (!dfn[u[i]])
            {
                Tarjan(u[i]);
                dfs(u[i], 0, d);
            }
        }
        for (int i = n + 1; i <= cnt; i++)
            T[i].clear();
        cnt = dfc = tp = 0;
        for (int i : num[d])
        {
            adj[u[i]].clear();
            adj[v[i]].clear();
            T[u[i]].clear();
            T[v[i]].clear();
            dfn[u[i]] = low[u[i]] = 0;
            dfn[v[i]] = low[v[i]] = 0;
        }
    }
    fill(f + 1, f + l + 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;
    int ans = 0;
    for (int i = 1; i <= l; i++)
        ans ^= f[i];
    cout << ans << '\n';
    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(nullptr);
    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 = 1; j * j <= i; j++)
        {
            if (i % j)
                continue;
            fac[i].push_back(j);
            if (j * j != i)
                fac[i].push_back(i / j);
        }
    }
    int t = 1;
    cin >> t;
    while (t--)
        solve();
}