#include <bits/stdc++.h>

using namespace std;

int mod = 998244353;

int sum(int x, int y) {
    if (x + y >= mod) {
        return x + y - mod;
    }
    return x + y;
}

int diff(int x, int y) {
    if (x - y < 0) {
        return x - y + mod;
    }
    return x - y;
}

int mult(int x, int y) {
    return (x * 1ll * y) % mod;
}

int k;

struct state {
    int same;
    int diff;

    state() : same(1), diff(0) {}
    state(int same_, int diff_) : same(same_), diff(diff_) {}

    void connect() {
        same = 0;
    }

    state operator*(const state & o) const {
        return state{sum(mult(same, o.same), mult(k - 1, mult(diff, o.diff))),
                sum(sum(mult(same, o.diff), mult(diff, o.same)), mult(k - 2, mult(diff, o.diff)))};
    }
};

state bamboo(int p) {
    state ans;
    state x{0, 1};
    while (p > 0) {
        if (p & 1) {
            ans = ans * x;
        }
        x = x * x;
        p >>= 1;
    }
    return ans;
}

void solve() {
    int n;
    int m;
    cin >> n >> m >> k;
    ++m;
    vector<pair<int, int>> p(2 * m);
    p[0] = {0, 1};
    p[1] = {n - 1, 0};
    for (int i = 1; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        if (u > v) {
            swap(u, v);
        }
        p[2 * i] = {u, 1};
        p[2 * i + 1] = {v, 0};
    }
    sort(p.begin(), p.end());
    stack<state> st;
    int prev = 0;
    st.push(state());
    for (auto & [x, type] : p) {
        if (type == 1) {
            state last = st.top();
            st.pop();
            st.push(last * bamboo(x - prev));
            st.push(state{});
        } else {
            state last = st.top();
            st.pop();
            last = last * bamboo(x - prev);
            last.connect();
            last = st.top() * last;
            st.pop();
            st.push(last);
        }
        prev = x;
    }
    cout << mult(st.top().diff, mult(k, k - 1)) << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
