#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int N=1e5+5,mod=1e9+7;
int T,n,m,a[N],b[N];
pii c[N],tj[N];
ll res,v,f[N];
void dfs(int i){
	if(i==n){
		for(int j=1;j<=n;j++)b[j]=a[j];
		for(int j=1;j<n;j++){
			if(b[j]==tj[j].first){
				if(!b[j+1])b[j+1]=tj[j].second;
				else if(b[j+1]!=tj[j].second)return ;
			}
		}
		res++;
		return ;
	}
	for(int k=1;k<=v;k++){
		for(int j=1;j<=v;j++){
			tj[i]={k,j};
			dfs(i+1);
		}
	}
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%d",&T);
	while(T--){
		res=0;
		scanf("%d%d%lld",&n,&m,&v);
		for(int i=1;i<=n;i++)a[i]=0;
		int flag=0;
		for(int i=1;i<=m;i++)scanf("%d%d",&c[i].first,&c[i].second);
		sort(c+1,c+m+1);
		for(int i=1;i<m;i++){
			if(c[i].first==c[i+1].first&&c[i].second!=c[i+1].second){
				printf("0\n");
				flag=1;
				break;
			}
			a[c[i].first]=c[i].second;
		}
		if(flag)continue;
		a[c[m].first]=c[m].second;
		dfs(1);
		printf("%lld\n",res);
	}
	return 0;
} 
