#include<cstdio>
#include<cstring>
#define _M_ 100005
#define _N_ 105
int n,m,v,c[_M_],d[_M_],val[_N_],a[_N_],b[_N_],ans;
void check(int now){
	if(now==n+1){
		for(int i=1;i<=m;i++)
			if(val[c[i]]!=d[i])
				return;
		for(int i=1;i<=n-1;i++)
			if(val[i]==a[i]&&val[i+1]!=b[i])
				return;
		throw 1;
	}
	for(int i=0;i<=v;i++){
		val[now]=i;
		check(now+1);
	}
}
void dfs1(int now){
	if(now==n){
		try{
			check(1);
		}catch(...){
			ans++;
		}
		return;
	}
	for(int i=1;i<=v;i++){
		for(int j=1;j<=v;j++){
			a[now]=i;
			b[now]=j;
			dfs1(now+1);
		}
	}
}
void work(){
	ans=0;
	scanf("%d%d%d",&n,&m,&v);
	for(int i=1;i<=m;i++)
		scanf("%d%d",c+i,d+i);
	dfs1(1);
	printf("%d\n",ans);
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	int t;
	scanf("%d",&t);
	while(t--)
		work();
	return 0;
}
