#include <bits/extc++.h>
#define dbg(x) cerr << #x" = " << (x) << endl
#define debug(...) fprintf(stderr,__VA_ARGS__)
using ll = long long;
const int MAXN = 1e9 + 10,MAXM = 1e5 + 10,MOD = 1e9 + 7;
using namespace std;
int n,m,v,c[MAXM],d[MAXM];
namespace BF{
	int a[15],b[15],ans,x[15],tmpx[15];
	// bool check1(){
	// 	for(int i = 1;i < n;i++){
	// 		if(tmpx[i] == a[i] && tmpx[i + 1] && tmpx[i + 1] != b[i]) return 0;
	// 	}
	// 	return 1;
	// }
	// bool dfsx(int u){
	// 	if(u >= n + 1){
	// 		if(check1()) return 1;
	// 		return 0;
	// 	}
	// 	if(x[u]) {
	// 		tmpx[u] = x[u];
	// 		if(x[u] == a[u]) {
	// 			tmpx[u + 1] = b[u];
	// 			return dfsx(u + 2);
	// 		} else return dfsx(u + 1);
	// 	}
	// 	for(tmpx[u] = 1;tmpx[u] <= v;tmpx[u]++){
	// 		if(dfsx(u + 1)) return 1;
	// 	}
	// 	return 0;
	// }
	bool check(){
		for(int i = 1;i < n;i++){
			if(tmpx[i] == a[i] && tmpx[i + 1] && tmpx[i + 1] != b[i]) return 0;
			if(tmpx[i] == a[i]) tmpx[i + 1] = b[i];
			// if(!dfsx(1)) return 0;
		}
		return 1;
	}
	void dfs(int u){
		if(u == n){
			memcpy(tmpx,x,sizeof x);
			ans += check();
			return;
		}
		for(a[u] = 1;a[u] <= v;a[u]++){
			for(b[u] = 1;b[u] <= v;b[u]++){
				dfs(u + 1);
			}
		}
	}
	void init(){
		memset(x,0,sizeof x);
		ans = 0;
	}
	void solve(){
		init();
		for(int i = 1;i <= m;i++) {
			if(x[c[i]] && x[c[i]] != d[i]) {
				cout << "0\n";
				return;
			}
			x[c[i]] = d[i];
		}
		dfs(1);
		cout << ans << '\n';
	}
}

void init0(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	cin.tie(0) -> ios::sync_with_stdio(0);
}

void init(){
	cin >> n >> m >> v;
	for(int i = 1;i <= m;i++) cin >> c[i] >> d[i];
}

void solve(){
	init();
	if(n <= 12 && m <= 12 && v <= 2) BF::solve();
	else {

	}
}

int main(){
	init0();
	int t;
	cin >> t;
	// t = 5;
	while(t--) solve();
}