#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <functional>

using namespace std;

const int MOD = 998244353;

long long binpow(long long a, long long p) {
	return p?binpow(a*a%MOD, p>>1)*(p&1?a:1)%MOD:1;
}

long long bininv(long long a) {
	return binpow(a, MOD-2);
}

int f(int n, int k) {
	// (k-1)^(n-2)-(k-1)^(n-3)+(k-1)^(n-4) 
	// ans * k = (k-1)^(n-1) +- 1
	int ans = binpow(k-1, n-1);
	if (n%2) ans = (ans + MOD-1)%MOD;
	else ans = (ans + 1) % MOD;
	return ans * bininv(k) % MOD;
}

void solve(int test_ind){
	int n, m, k;
	cin >> n >> m >> k;
	if (m == 0) {
		cout << f(n, k) * (k-1ll)%MOD * k%MOD << endl;
		return;
	}
	map<int, set<int> > g;
	for (int i=0;i<m;++i) {
		int u, v;
		cin >> u >> v;
		--u;--v;
		g[u].insert((v+n-u)%n);
		g[v].insert((u+n-v)%n);
	}
	set<int> vis;
	int ans = 1;
	for (auto it=g.begin();it!=g.end();++it){
		if (vis.count(it->first)) continue;
		auto it2 = it;
		it2++;
		if (it2 == g.end()) it2 = g.begin();
		int d = (it2->first - it->first + n) % n;
		int v = (d + 1);

		int prv = *it2->second.rbegin();
		int nxt = (it2->first + prv) % n;
		// cerr << it->first << " " << nxt << " " << v << endl;

		while (nxt != it->first) {
			auto it3 = g.find(nxt);
			auto its = it3->second.lower_bound(n - prv);
			if (its == it3->second.begin()) {
				vis.insert(nxt);
				it3 = g.upper_bound(nxt);
				if (it3 == g.end()) it3 = g.begin();
				v += (it3->first + n - nxt) % n;
				nxt = it3->first;
				prv = -1;
			} else {
				--its;
				v++;
				prv = *its;
				nxt = (nxt + prv) % n;
			}
			// cerr << it->first << " " << nxt << " " << v << " " << prv << endl;
		}
		// cerr << v << endl;
		ans = ans * 1ll * f(v, k) % MOD;
	}
	cout << ans * (k-1ll)%MOD * k%MOD << endl;
}

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int t=1;
	cin >> t;
	for(int i=0;i<t;i++){
		solve(i);
	}
	return 0;
}
