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

typedef long long ll;

ll getInt() {
	ll s = 0, f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar())
		if (c == '-') f = -1;
	for (; isdigit(c); c = getchar())
		s = s * 10 + c - '0';
	return s * f;
}

const int N = 1e5 + 10;

ll c[N], d[N];

namespace Solve1 {
	ll n, m, v;
	ll ans = 0;
	
	pair<ll, ll> lim[N];
	
	ll res[N];
	ll res_[N];
	
	bool check() {
		memcpy(res, res_, sizeof res_);
		for (int i = 1; i < n; ++i) {
			if (res[i] == lim[i].first) {
				if (res[i + 1] == 0 || res[i + 1] == lim[i].second) {
					res[i + 1] = lim[i].second;
				} else {
					return 0;
				}
			}
		}
		return 1;
	} 
	
	void dfs(ll x) {
		if (x == n) {
			if (check()) {
				++ans;
			}
			return;
		}
		
		for (int a = 1; a <= v; ++a) {
			for (int b = 1; b <= v; ++b) {
				lim[x] = make_pair(a, b); 
				dfs(x + 1);
			}
		}
	}
	
	void work() {
		ans = 0;
		memset(res_, 0, sizeof res);
		n = getInt(), m = getInt(), v = getInt();
		for (int i = 1; i <= m; ++i) {
			c[i] = getInt();
			d[i] = getInt();
			if (res_[c[i]] && res_[c[i]] != d[i]) {
				puts("0");
				return;
			}
			res_[c[i]] = d[i];
		}
		dfs(1); 
		cout << ans << endl;
	}
}



int main() {
	freopen("assign.in", "r", stdin);
	freopen("assign.out", "w", stdout);
	ll t = getInt();
	while (t--) {
		Solve1::work();
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}
