#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], w[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;
struct graph
{
    int head[N], nxt[N], to[N], tot, siz[N];
    void add(int x, int y)
    {
        nxt[tot] = head[x], to[tot] = y, head[x] = tot++;
        nxt[tot] = head[y], to[tot] = x, head[y] = tot++;
        siz[x]++;
        siz[y]++;
    }
} adj, T;

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