#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
int a[MAXN];
int n, m, v;
int ans = 0;
int check(){
	int s = 1;
	for(int i = 1; i < n; i++){
		int f = 0;
		for(int x = 1; x <= v; x++){
			for(int y = 1; y <= v; y++){
				if(a[i] != x || (a[i] == x && a[i + 1] == y)){
					f++;
				}
			}
		}
		s *= f;
	}
	return s;
}
inline void dfs(int f){
	if(f > n){
		ans += check();
		return;
	}
	if(a[f] != 0){
		dfs(f + 1);
	}
	else{
		for(int i = 1; i <= v; i++){
			a[f] = i;
			dfs(f + 1);
		}
		a[f] = 0;
	}
	return;
}
int main(){
	freopen("assign.in", "r", stdin);
	freopen("assign.out", "w", stdout); 
	int T;
	cin >> T;
	while(T--){
		ans = 0;
		memset(a, 0, sizeof(0));
		cin >> n >> m >> v;
		int flag = 0;
		for(int i = 1; i <= m; i++){
			int x, y;
			cin >> x >> y;
			if(!a[x]){
				a[x] = y;
			}
			else{
				if(a[x] != y){
					flag = 1;
				}
			}
		}
		if(flag == 1){
			cout << 0 << "\n";
			continue;
		}
		dfs(1);
		cout << ans;
	}
	return 0;
}
/*
1
10 11 2
10 2
7 2
7 2
2 2
3 2
4 3
10 2
7 2
10 2
3 2
3 2
*/
