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


template <int MOD_> struct modnum {
	static constexpr int MOD = MOD_;
	static_assert(MOD_ > 0, "MOD must be positive");

private:
	using ll = long long;

	int v;

	static int minv(int a, int m) {
		a %= m;
		assert(a);
		return a == 1 ? 1 : int(m - ll(minv(m, a)) * ll(m) / a);
	}

public:

	modnum() : v(0) {}
	modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
	explicit operator int() const { return v; }
	friend std::ostream& operator << (std::ostream& out, const modnum& n) { return out << int(n); }
	friend std::istream& operator >> (std::istream& in, modnum& n) { ll v_; in >> v_; n = modnum(v_); return in; }

	friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
	friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }

	modnum inv() const {
		modnum res;
		res.v = minv(v, MOD);
		return res;
	}
	friend modnum inv(const modnum& m) { return m.inv(); }
	modnum neg() const {
		modnum res;
		res.v = v ? MOD-v : 0;
		return res;
	}
	friend modnum neg(const modnum& m) { return m.neg(); }

	modnum operator- () const {
		return neg();
	}
	modnum operator+ () const {
		return modnum(*this);
	}

	modnum& operator ++ () {
		v ++;
		if (v == MOD) v = 0;
		return *this;
	}
	modnum& operator -- () {
		if (v == 0) v = MOD;
		v --;
		return *this;
	}
	modnum& operator += (const modnum& o) {
		v += o.v;
		if (v >= MOD) v -= MOD;
		return *this;
	}
	modnum& operator -= (const modnum& o) {
		v -= o.v;
		if (v < 0) v += MOD;
		return *this;
	}
	modnum& operator *= (const modnum& o) {
		v = int(ll(v) * ll(o.v) % MOD);
		return *this;
	}
	modnum& operator /= (const modnum& o) {
		return *this *= o.inv();
	}

	friend modnum operator ++ (modnum& a, int) { modnum r = a; ++a; return r; }
	friend modnum operator -- (modnum& a, int) { modnum r = a; --a; return r; }
	friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
	friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
	friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
	friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
};

template <typename T> T pow(T a, long long b) {
	assert(b >= 0);
	T r = 1; while (b) { if (b & 1) r *= a; b >>= 1; a *= a; } return r;
}

using num = modnum<998244353>;


#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;

vector<num> berlekampMassey(vector<num> s) {
	int n = sz(s), L = 0, m = 0;
	vector<num> C(n), B(n), T;
	C[0] = B[0] = 1;

	num b = 1;
	rep(i,0,n) { ++m;
		num d = s[i];
		rep(j,1,L+1) d = (d + C[j] * s[i - j]);
		if (d == 0) continue;
		T = C; num coef = d / b;
		rep(j,m,n) C[j] = (C[j] - coef * B[j - m]);
		if (2 * L > i) continue;
		L = i + 1 - L; B = T; b = d; m = 0;
	}

	C.resize(L + 1); C.erase(C.begin());
	for (num& x : C) x = -x;
	return C;
}

using ll = int64_t;
typedef vector<num> Poly;
num linearRec(Poly S, Poly tr, ll k) {
	int n = sz(tr);

	auto combine = [&](Poly a, Poly b) {
		Poly res(n * 2 + 1);
		rep(i,0,n+1) rep(j,0,n+1)
			res[i + j] = (res[i + j] + a[i] * b[j]);
		for (int i = 2 * n; i > n; --i) rep(j,0,n)
			res[i - 1 - j] = (res[i - 1 - j] + res[i] * tr[j]);
		res.resize(n + 1);
		return res;
	};

	Poly pol(n + 1), e(pol);
	pol[0] = e[1] = 1;

	for (++k; k; k /= 2) {
		if (k % 2) pol = combine(pol, e);
		e = combine(e, e);
	}

	num res = 0;
	rep(i,0,n) res = (res + pol[i + 1] * S[i]);
	return res;
}

void solve(){
	int N, M, K;
	cin >> N >> M >> K;
	vector<num> vals = {1};
	vector<pair<int,int> > edges;
	edges.push_back({0, N-1});
	for(int i = 0; i < M; i++){
		int a, b;
		cin >> a >> b;
		a--; b--;
		edges.push_back({a, b});
	}
	set<pair<int,int> > seen;
	sort(edges.begin(), edges.end(), [&](pair<int,int> a, pair<int,int> b){
		return pair<int,int>{-a.first, a.second} < pair<int,int>{-b.first, b.second};
	});

	vector<int> ls;
	for(auto [x, y] : edges){
		int l = y-x+1;

		while(true){
			auto v = seen.lower_bound({x, -1});
			if(v == seen.end()) break;
			if(v->second <= y) {
				l -= (v->second - v->first - 1);
				seen.erase(v);
			} else {
				break;
			}
		}
		seen.insert({x, y});
		ls.push_back(l);
	}
	assert(seen == (set<pair<int,int>>{{0, N-1}}));
	num ans = num(K) * num(K-1);
	vector<num> s {0, 1};
	vector<num> tr {K-2, K-1};
	for(int l : ls){
		ans *= linearRec(s, tr, l-1);
	}
	cout << ans << '\n';
}

int main(){
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	int T;
	cin >> T;
	while(T--) solve();
}
