#include <bits/stdc++.h>
using namespace std;
using ll = long long; using ull = unsigned long long;
using pll = pair<ll, ll>; using ld = long double;
void fileIO(const string& x) { freopen((x + ".in").c_str(), "r", stdin), freopen((x + ".out").c_str(), "w", stdout); }
template<typename T1, typename T2> bool chkmin(T1& x, const T2& y) { bool flag = (y < x); x = (y < x) ? y : x; return flag; }
template<typename T1, typename T2> bool chkmax(T1& x, const T2& y) { bool flag = (y > x); x = (y > x) ? y : x; return flag; }
mt19937_64 rnd(random_device{}());

const ll N = 100 + 5, M = 1e5 + 5;

ll test_case, ans, n, m, v, val[N], a[N], b[N], c[M], d[M];

void dfs(ll stp) {
	if(stp == n ) {
		for(int i = 1; i <= n; i++) val[i] = -1;
		for(int i = 1; i <= m; i++) val[c[i]] = d[i];
		for(int i = 1; i < n; i++) {
			if(val[i] == -1) val[i] = a[i] == 1 ? 2 : 1;
			else if(val[i] == a[i]) {
				if(val[i + 1] == -1 || val[i + 1] == b[i]) val[i + 1] = b[i];
				else return;
			}
		}
		for(int i = 1; i < n; i++) {
			//cout << a[i] << " " << b[i] << "\n";
		}
		ans++;
		return;
	}
	for(int i = 1; i <= v; i++) {
		for(int j = 1; j <= v; j++) {
			a[stp] = i, b[stp] = j;
			dfs(stp + 1);
		}
	}
}

void solution() {
	cin >> n >> m >> v;
	ans = 0;
	unordered_map<ll, ll> mp; bool flag = false;
	for(int i = 1; i <= m; i++) {
		cin >> c[i] >> d[i];
		if(mp.find(c[i]) != mp.end() && mp[c[i]] != d[i]) flag = true;
		mp[c[i]] = d[i];
	}
	if(flag) {
		cout << "0\n";
		return;
	}
	if((n + m) * pow(v, n * 2.0) >= 1e9) {
		cout << "-1\n";
		return;
	}
	dfs(1);
	cout << ans << "\n";
}

double start_time, end_time;
int main() {
	fileIO("assign");
	ios::sync_with_stdio(false), cin.tie(nullptr);
	start_time = clock(); cin >> test_case; while(test_case--) solution(); end_time = clock();
	return 0;
}