import java.io.*;
import java.util.*;

public class Main {
	BufferedReader in;
	PrintWriter out;

	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;
		}
		return x - y + mod;
	}

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

	int k;

	public class State {
		int same;
		int diff;

		public State() {
			same = 1;
			diff = 0;
		}

		public State(int same, int diff) {
			this.same = same;
			this.diff = diff;
		}

		public State connect() {
			return new State(0, diff);
		}

		public State merge(State o) {
			return new State(sum(mult(same, o.same), mult(k - 1, mult(diff, o.diff))),
					sum(sum(mult(same, o.diff), mult(diff, o.same)), mult(mult(diff, o.diff), k - 2)));
		}
	}

	public State bamboo(int p) {
		State res = new State();
		State pow = new State(0, 1);
		while (p > 0) {
			if (p % 2 == 1) {
				res = res.merge(pow);
			}
			pow = pow.merge(pow);
			p /= 2;
		}
		return res;
	}
	
	public class Edge implements Comparable<Edge> {
		int u;
		int v;
		
		public Edge(int u, int v) {
			this.u = u;
			this.v = v;
		}

		@Override
		public int compareTo(Edge o) {
			if (u != o.u) {
				return u - o.u;
			}
			if (v < u) {
				if (o.v > u) {
					return -1;
				}
				return o.v - v;
			}
			if (o.v < u) {
				return 1;
			}
			return o.v - v;
		}
	}
	
	public class Point implements Comparable<Point> {
		int x;
		int type;
		
		public Point(int x, int type) {
			this.x = x;
			this.type = type;
		}

		@Override
		public int compareTo(Point o) {
			if (x != o.x) {
				return x - o.x;
			}
			return type - o.type;
		}
		
	}
	
	public void solve() throws IOException {
		StringTokenizer st = new StringTokenizer(in.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken()) + 1;
		k = Integer.parseInt(st.nextToken());
		Point[] p = new Point[2 * m];
		p[0] = new Point(0, 1);
		p[1] = new Point(n - 1, 0);
		for (int i = 1; i < m; ++i) {
			st = new StringTokenizer(in.readLine());
			int u = Integer.parseInt(st.nextToken()) - 1;
			int v = Integer.parseInt(st.nextToken()) - 1;
			if (u > v) {
				int w = u;
				u = v;
				v = w;
			}
			p[2 * i] = new Point(u, 1);
			p[2 * i + 1] = new Point(v, 0);
		}
		Arrays.sort(p);
		Stack<State> states = new Stack<>();
		int prev = 0;
		states.add(new State());
		for (Point point : p) {
			if (point.type == 1) {
				states.add(states.pop().merge(bamboo(point.x - prev)));
				states.add(new State());
			} else {
				State cur = states.pop().merge(bamboo(point.x - prev)).connect();
				states.add(states.pop().merge(cur));
			}
			prev = point.x;
		}
		out.println(mult(states.pop().diff, mult(k, k - 1)));
	}

	public void run() {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
			int t = Integer.parseInt(in.readLine());
			for (int i = 0; i < t; ++i) {
				solve();
			}
			in.close();
			out.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	public static void main(String[] args) {
		new Main().run();
	}

}
