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

public class CrenameEXP {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int tests = in.nextInt();
		for (int t = 0; t < tests; ++t) {
			int n = in.nextInt();
			int m = in.nextInt();
			int k = in.nextInt();
			int[][] edges = new int[m][2];
			for (int i = 0; i < m; ++i) {
				edges[i][0] = in.nextInt() - 1;
				edges[i][1] = in.nextInt() - 1;
			}
			int INF = 1000000000;
			int max = 1;
			for (int i = 0; i < n; ++i) {
			    if (INF / k < max) {
			        max = INF;
			    } else {
				    max *= k;
			    }
			}
			int ans = 0;
			int[] c = new int[n];
			for (int mask = 0; mask < max; ++mask) {
				int cur = mask;
				for (int i = 0; i < n; ++i) {
					c[i] = cur % k;
					cur /= k;
				}
				boolean good = c[0] != c[n - 1];
				for (int i = 0; i < n - 1; ++i) {
					if (c[i] == c[i + 1]) {
						good = false;
						break;
					}
				}
				if (!good) {
					continue;
				}
				for (int i = 0; i < m; ++i) {
					if (c[edges[i][0]] == c[edges[i][1]]) {
						good = false;
						break;
					}
				}
				if (good) {
					++ans;
				}
			}
			out.println(ans);
		}
		in.close();
		out.close();
	}

}
