#include <bits/stdc++.h>
#define ll long long
#define N 100005
using namespace std;
int T,n,m,v,a[N],f[N],f2[N],b[N],c[N],ans;
const int mod=1e9+7;
bool tot;
void dfs(int t){
	if(t>=n){
//		cout<<endl;
//		for(int i=1;i<n;i++){
//			cout<<f[i]<<" "<<f2[i]<<endl;
//		} 
		for(int i=1;i<=v;i++) b[i]=0;
		for(int i=1;i<n;i++){
			if(b[f[i]]==0) b[f[i]]=f2[i];
			else if(b[f[i]]!=f2[i]) return ;
		}
		bool tot=0;
		for(int i=1;i<=n;i++){
			if(a[i]>0) tot=1;
			if(!tot) continue;
			if(a[i]>0){
				if(b[c[i-1]]!=0&&b[c[i-1]]!=a[i]&&i!=1) return ;
				c[i]=a[i];
			}
			else c[i]=b[c[i-1]];
		}
//		cout<<1<<endl;
		ans++;
	}
	else {
		for(int i=1;i<=v;i++){
			f[t]=i;
			for(int j=1;j<=v;j++){
				f2[t]=j;
				dfs(t+1);
			} 
		} 
	}
	return ;
}
signed main(){
	freopen("assign.in","r",stdin);
//	freopen("assign2.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%d",&T);
	int x,y;
	while(T--){
		scanf("%d%d%d",&n,&m,&v);
		for(int i=1;i<=n;i++) a[i]=0;
		tot=0;
		for(int i=1;i<=m;i++){
			scanf("%d%d",&x,&y);
			if(a[x]!=0&&a[x]!=y) tot=1; 
			a[x]=y;
		}
		if(tot){
			printf("0\n");
			continue;
		}
		ans=0;
		dfs(1);
		printf("%d\n",ans);
	}
	return 0;
}
/*
1
5 1 2
1 2
*/
