#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
int c[maxn],d[maxn];
int n,m,v;
int cnt,ans;
int x[maxn],y[1005][5],t[1005][3],vis[maxn];
bool judge(){
	for(int i=1;i<=m;i++)if(x[c[i]]!=d[i])return false;
	return true;
}
bool check(int p){
	for(int i=1;i<=n-1;i++){
		if(x[i]==t[p][1]&&x[i+1]!=t[p][2])return false;
	}
	//cout<<t[p][1]<<" "<<t[p][2]<<"\n";
	vis[p]=1;
	return true;
}
void dfs(int pos){
	if(pos==n+1){
		if(judge()){
			//exit(0);
			for(int i=1;i<=cnt;i++){
				if(vis[i])continue;
				if(check(i))ans++;
			}
		}
		return; 
	}
	for(int i=1;i<=v;i++){
		x[pos]=i;
		dfs(pos+1);
		x[pos]=0;
	}
	return;
}
void sol(){
	cin>>n>>m>>v;
	for(int i=1;i<=m;i++){
		cin>>c[i]>>d[i];
	}
	cnt=0,ans=0;
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=v;i++){
		for(int j=1;j<=v;j++){
			t[++cnt][1]=i;
			t[cnt][2]=j;
		}
	}
	dfs(1);
	cout<<ans<<"\n";
} 
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	int t;
	cin>>t;
	while(t--){
		sol();
		
	}
	return 0;
}
/*
3
2 1 2
1 1
2 2 2
1 1
2 2
2 2 2
1 1
1 2

1
2 1 2
1 1

1
2 2 2
1 1
2 2
*/

