#include <bits/stdc++.h>
using namespace std;

constexpr int64_t MAXN = 2e5 + 5, MAXV = 1e5 + 5, mod = 998244353;
int n, m, L;
int st[MAXN], tp, low[MAXN], num[MAXN], dfn, nn;
int prime[MAXV], mu[MAXN];
bool vis[MAXV];
int64_t ans[MAXN], dp[MAXN];
vector<int> fac[MAXV];
vector<pair<int, int>> e[MAXN];
int head1[MAXN], head2[MAXN], tot1 = 1, tot2 = 1;
struct Edge
{
    int to, next;
} e1[MAXN << 3], e2[MAXN << 3];
void add1(int u, int v) { e1[++tot1].to = v, e1[tot1].next = head1[u], head1[u] = tot1; }
void add2(int u, int v) { e2[++tot2].to = v, e2[tot2].next = head2[u], head2[u] = tot2; }

namespace fastIO
{
#ifndef LOCAL
#define getchar() p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++
#define putchar(x) (p3 - obuf < 1000000) ? (*p3++ = x) : (fwrite(obuf, p3 - obuf, 1, stdout), p3 = obuf, *p3++ = x)
    char buf[1000000], *p1 = buf, *p2 = buf, obuf[1000000], *p3 = obuf;
    inline void flush() { fwrite(obuf, p3 - obuf, 1, stdout); }
#endif
    inline int read()
    {
        int s = 0;
        char ch = getchar();
        while (ch < '0' || ch > '9')
            ch = getchar();
        while (ch >= '0' && ch <= '9')
        {
            s = s * 10 + ch - '0';
            ch = getchar();
        }
        return s;
    }
    inline void write(int64_t x)
    {
        if (x > 9)
            write(x / 10);
        putchar(x % 10 + '0');
    }
};
using namespace fastIO;

void init()
{
    mu[1] = 1;
    for (int i = 2; i < MAXV; i++)
    {
        if (!vis[i])
            prime[++prime[0]] = i, mu[i] = -1;
        for (int j = 1; j <= prime[0] && i * prime[j] < MAXV; j++)
        {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0)
            {
                mu[i * prime[j]] = 0;
                break;
            }
            else
                mu[i * prime[j]] = -mu[i];
        }
    }
    for (int i = 1; i < MAXV; i++)
        for (int j = i; j < MAXV; j += i)
            fac[j].push_back(i);
}

void tarjan(int v) // 广义圆方树
{
    low[v] = num[v] = ++dfn;
    st[++tp] = v;
    for (int i = head1[v]; i; i = e1[i].next)
    {
        int u = e1[i].to;
        if (!num[u])
        {
            tarjan(u);
            low[v] = min(low[u], low[v]);
            if (low[u] >= num[v])
            {
                ++nn;
                int z;
                do
                {
                    z = st[tp--], add2(z, nn), add2(nn, z);
                } while (z != u);
                add2(v, nn), add2(nn, v);
            }
        }
        else
            low[v] = min(low[v], num[u]);
    }
}

void dfs(int v, int fa, int id)
{
    for (int i = head2[v]; i; i = e2[i].next)
    {
        int u = e2[i].to;
        if (u != fa)
            dfs(u, v, id);
    }

    if (v <= n) // 圆点
    {
        dp[v] = 1;
        for (int i = head2[v]; i; i = e2[i].next)
        {
            int u = e2[i].to;
            if (u == fa)
                continue;
            ans[id] = (ans[id] + dp[v] * dp[u] % mod) % mod;
            dp[v] = (dp[v] + dp[u]) % mod;
        }
    }
    else // 方点，看是否对应环
    {
        dp[v] = 0;
        int deg = 0;
        for (int i = head2[v]; i; i = e2[i].next)
            ++deg;
        if (deg == 2) // 不对应，直接继承子结点dp值
        {
            for (int i = head2[v]; i; i = e2[i].next)
            {
                int u = e2[i].to;
                if (u != fa)
                    dp[v] = dp[u];
            }
        }
        else // 对应一个环，考虑除父结点外的环点对答案的贡献
        {
            for (int i = head2[v]; i; i = e2[i].next)
            {
                int u = e2[i].to;
                if (u == fa)
                    continue;
                ans[id] = (ans[id] + dp[v] * dp[u] % mod) % mod;
                dp[v] = (dp[v] + 2 * dp[u] % mod) % mod;
            }
        }
    }
}

int main()
{
    init();
    int t = read();
    while (t--)
    {
        n = read(), m = read(), L = read();
        while (m--)
        {
            int v = read(), u = read(), w = read();
            for (auto i : fac[w])
                e[i].emplace_back(v, u);
        }
        vector<int> vec;
        for (int i = 1; i <= L; i++)
        {
            for (auto [v, u] : e[i])
            {
                add1(v, u), add1(u, v);
                vec.push_back(v), vec.push_back(u);
            }
            nn = n, dfn = 0;
            for (auto v : vec)
                if (!num[v])
                    tp = 0, tarjan(v), dfs(v, 0, i);
            for (auto v : vec)
                head1[v] = head2[v] = num[v] = 0;
            for (int i = nn; i > n; i--)
                head2[i] = 0;
            tot1 = tot2 = 1;
            e[i].clear(), vec.clear();
        }

        int64_t res = 0;
        for (int i = 1; i <= L; i++)
        {
            for (int j = 2; i * j <= L; j++)
                ans[i] += (mu[j] * ans[i * j]) % mod + mod, ans[i] %= mod;
            res ^= ans[i];
        }
        write(res), putchar('\n');
        fill(ans + 1, ans + L + 1, 0);
    }
    flush();

    return 0;
}