#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
const int mod = 998244353;
const int maxn = 500025;

vector<int> tr[maxn * 2];
int value[maxn * 2];
void add_edge(int a, int b) {
    // cerr << a - maxn << " -> " << b << endl;
    tr[a].emplace_back(b);
    tr[b].emplace_back(a);
}

pair<int64_t,int64_t> tree_dfs(int i, int f) {
    // cerr << "value = " << value[i] << endl;
    // cerr << "i = " << i << endl;
    int64_t D = (i < maxn);
    int64_t T = 0;
    for (int j: tr[i]) {
        if (j == f) continue;
        auto [d, t] = tree_dfs(j, i);
        T += t + d * D * value[i];
        D += d;
        T %= mod;
        D %= mod;
        // TODO
    }
    D = D * value[i] % mod;
    return {D, T};
}

vector<int> g[maxn];
vector<pair<int,int>> es[maxn];
int vis[maxn], low[maxn], tot;
int vid;

int modadd(int a, int b) {
    return a + b >= mod ? a + b - mod : a + b;
}
int modsub(int a, int b) {
    return a - b < 0 ? a - b + mod : a - b;
}

vector<int> stk, all;
void dfs(int i) {
    vis[i] = low[i] = ++tot;
    all.push_back(i);
    stk.emplace_back(i);
    value[i] = 1;
    for (int j: g[i]) {
        if (!vis[j]) {
            dfs(j);
            low[i] = min(low[i], low[j]);
            if (low[j] >= vis[i]) {
                int bcc = ++vid;
                all.push_back(bcc);
                int x;
                int c = 1;
                do {
                    x = stk.back(); stk.pop_back();
                    ++c;
                    add_edge(bcc, x);
                } while (x != j);
                add_edge(bcc, i);
                // cerr << "c = " << c << endl;
                if (c == 2) {
                    value[bcc] = 1;
                } else {
                    value[bcc] = 2;
                }
            }
        } else {
            low[i] = min(low[i], vis[j]);
        }
    }
}

int solve(int s) {
    vid = maxn;

    dfs(s);
    int res = tree_dfs(s, -1).second;
    for (int v: all) tr[v].clear();
    stk.clear();
    all.clear();
    return res;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        int n, m, L;
        cin >> n >> m >> L;
        for (int i = 0; i < m; i++) {
            int u, v, w;
            cin >> u >> v >> w;
            es[w].emplace_back(u, v);
        }

        vector<int> ans(L + 1);
        for (int d = 1; d <= L; d++) {
            vector<pair<int,int>> ee;
            for (int i = d; i <= L; i += d) {
                for (const auto &e: es[i])
                    ee.emplace_back(e);
            }

            for (auto [a, b]: ee) {
                g[a].push_back(b);
                g[b].push_back(a);
                vis[a] = vis[b] = 0;
            }
            tot = 0;
            for (auto [a, b]: ee) {
                if (!vis[a]) ans[d] = modadd(ans[d], solve(a));
                if (!vis[b]) ans[d] = modadd(ans[d], solve(b));
            }
            for (auto [a, b]: ee) {
                g[a].clear();
                g[b].clear();
            }
        }

        // for (int d = 1; d <= L; d++)
        //     cerr << ans[d] << ' ';
        // cerr << endl;

        for (int d = L; d >= 1; d--) {
            for (int i = d * 2; i <= L; i += d) {
                ans[d] = modsub(ans[d], ans[i]);
            }
        }

        // for (int d = 1; d <= L; d++)
        //     cerr << ans[d] << ' ';
        // cerr << endl;

        int res = 0;
        for (int d = 1; d <= L; d++)
            res ^= ans[d];
        cout << res << '\n';

        for (int i = 1; i <= L; i++)
            es[i].clear();
    }
    return 0;
}