#include <iomanip>
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <set>
//#include <multiset>
#include <map>
#include <utility>
#include <numeric>
#include "queue"
#include <cassert>
#ifndef __clang__
#include <bits/stdc++.h>
#endif
using namespace std;
constexpr int mod = 998244353;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#define debugf(s, ...) fprintf(stderr, "(" #__VA_ARGS__ ") " s "\n", __VA_ARGS__)

#define rs ranges::

#define CE constexpr


using i64 = int64_t;

struct imt {
    int val = 0;
    CE imt() = default;
    CE imt(int x): val(x < 0 ? x + mod : x) {
    }

    template <typename T>
    CE imt(T x) : imt(int(x % mod)) {
    }

    CE imt &operator+=(const imt &a) {
        val += a.val;
        if (val >= mod) val -= mod;
        return *this;
    }

    CE imt &operator-=(const imt &a) {
        val -= a.val;
        if (val < 0) val += mod;
        return *this;
    }

    CE imt &operator*=(const imt &a) {
        val = val * 1LL * a.val % mod;
        return *this;
    }

    CE friend imt operator+(const imt &a, const imt &b) {
        return imt(a) += b;
    }

    CE friend imt operator-(const imt &a, const imt &b) {
        return imt(a) -= b;
    }

    CE friend imt operator*(const imt &a, const imt &b) {
        return imt(a) *= b;
    }

    CE imt pow(i64 x) const {
        x %= mod - 1;
        if (x < 0) x += mod - 1;
        imt cur = *this;
        imt res = 1;
        while (x > 0) {
            if (x & 1) res *= cur;
            cur *= cur;
            x >>= 1;
        }
        return res;
    }

    CE imt inv() const {
        return pow(mod - 2);
    }

    CE imt &operator/=(const imt &a) {
        return *this *= a.inv();
    }

    CE friend imt operator/(const imt &a, const imt &b) {
        return imt(a) /= b;
    }
};

using mt = std::array<std::array<imt, 2>, 2>;
using mr = array<imt, 2>;

mt operator*(const mt &x, const mt &y) {
    mt res;
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            for (int k = 0; k < 2; ++k) {
                res[i][k] += x[i][j] * y[j][k];
            }
        }
    }
    return res;
}

imt formula(int n, int k) {
    mt cur{mr{0, 1}, mr{k - 1, k - 2}};
    mt res{mr{1, 0}, mr{0, 1}};

    while (n > 0) {
        if (n & 1) res = res * cur;
        cur = cur * cur;
        n >>= 1;
    }
//    debugf("[%d %d] [%d %d]", res[0][0].val, res[0][1].val, res[1][0].val, res[1][1].val);
    return res[0][0] * k;
}

struct edge_t {
    int from, to;
};

bool operator<(const edge_t &a, const edge_t &b) {
    if (a.from != b.from) {
        debugf("%d %d", a.from, b.from);
        assert(false);
        return false;
    }
    if (a.to - a.from < 0 && b.to - b.from > 0) return true;
    if (a.to - a.from > 0 && b.to - b.from < 0) return false;

    return a.to - a.from > b.to - b.from;
}

void solve(int tc) {
    int n, m, k;
    cin >> n >> m >> k;

    if (m == 0) {
        cout << formula(n, k).val << '\n';
        return;
    }

    map<int, set<edge_t>> edges;

    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        --x;
        edges[x].insert({x, --y});
        edges[y].insert({y, x});
    }

    set<pair<int, int>> deleted_edges;

    for (auto &[x, s]: edges) {
        s.insert({x, x + 1});
    }

    imt res(1);
    for (auto it = edges.begin(); it != edges.end(); ++it) {
        auto &outgoing = it->second;
        auto v = it->first;

        for (auto [_, w]: outgoing) {
            if (deleted_edges.contains({v, w}))
                continue;
            int cur = w;
            int prv = v;
            int cnt = 0;
            do {
                deleted_edges.emplace(prv, cur);
                int nxt;
                if (cur == prv + 1) {
                    auto cur_ = edges.lower_bound(cur);
                    cur = cur_ == edges.end() ? edges.begin()->first : cur_->first;
                    int len = cur - prv;
                    cnt += len < 0 ? len + n : len;
                    nxt = edges[cur].begin()->to;
                } else {
                    cnt += 1;
                    nxt = edges[cur].upper_bound({cur, prv})->to;
                }
                prv = cur;
                cur = nxt;
            } while (prv != v);
            res *= formula(cnt, k) / k / (k - 1);
        }

    }

    cout << (res * k * (k - 1)).val << '\n';

}
signed main() {
#ifndef __clang__
    cin.tie(0);
    ios_base::sync_with_stdio(0);
#endif

    int t = 1;
    cin >> t;
    for (int i = 0; i < t; ++i) solve(i);
    //pointd p = {5.7, -3};
}
