//f_{i,0} 表示 c_{i} 没被激活的方案数
//f_{i,1} 表示 c_{i} 被激活的方案数
//第一种：直接激活，c_{i} 激活链到 c_{i+1}
//如果没有固定，贪心选择不符合就行了 
#include<bits/stdc++.h>
using namespace std;
const int N=100010,MO=1e9+7;
int Q,n,m,v,ans,cc,c[N],d[N],a[N],b[N],x[N];
map<int,int> p;
int fp(int x,int y){
	int t=1;
	while(y){
		if(y&1) t=1ll*t*x%MO;
		x=1ll*x*x%MO,y>>=1;
	}
	return t;
} 
void check(){
	for(int i=1;i<=n;i++) x[i]=0;
	for(int i=1;i<=m;i++) x[c[i]]=d[i];
//	printf("------\n");
//	for(int i=1;i<n;i++){
//		printf("%d %d\n",a[i],b[i]);
//	}
//	printf("------\n");
	for(int i=1;i<=n-1;i++){
		if(!x[i]) continue;
		if(x[i]==a[i]&&x[i+1]!=b[i]&&x[i+1]) return ;
	}
	ans++; 
}
void dfs(int x){
	if(x==n){
		check();
	}else{
		for(int i=1;i<=v;i++){
			for(int j=1;j<=v;j++){
				a[x]=i,b[x]=j;
				dfs(x+1);
			}
		}
	}
} 
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%d",&Q);
	while(Q--){
		scanf("%d%d%d",&n,&m,&v);
		bool is=false;
		p.clear();
		for(int i=1;i<=m;i++){
			scanf("%d%d",&c[i],&d[i]);
			if(p.find(c[i])!=p.end()&&p[c[i]]!=d[i]) is=true;
			p[c[i]]=d[i];
		}
		if(is){
			printf("0\n");
			continue;
		}
		if(n<=12){
			ans=0;
			dfs(1);
			printf("%d\n",ans);
		}
	}
	return 0;
}
