#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int mod=1e9+7;
int T,n,m,v;
struct node{
	int c,d;
}g[100005];
bool cmp(node x,node y){
	if(x.c!=y.c) return x.c<y.c;
	else return x.d<y.d;
}
struct dd{
	int a,b;
}gg[100005];
int bz[100005],e[100005],ans;
void check(){
	for(int i=1;i<=n;i++) e[i]=bz[i];
	for(int i=1;i<n;i++){
		if(e[i]!=0){
			if(e[i]==gg[i].a){
				if(e[i+1]!=0&&e[i+1]!=gg[i].b) return;
				else e[i+1]=gg[i].b;
			}
		}
	}
	ans++;
}
void dfs(int u){
	if(u==n){
		check();
		return;
	}
	for(int i=1;i<=v;i++){
		for(int j=1;j<=v;j++){
			gg[u].a=i,gg[u].b=j;
			dfs(u+1);
		}
	}
}
void work(){
	for(int i=1;i<=m;i++) bz[i]=0;
	scanf("%d%d%d",&n,&m,&v);
	for(int i=1;i<=m;i++) scanf("%d%d",&g[i].c,&g[i].d);
	sort(g+1,g+m+1,cmp);
	for(int i=1;i<=m;i++){
		if(g[i].c==g[i-1].c&&g[i].d!=g[i-1].d){
			printf("0\n");
			return;
		}
	}
	for(int i=1;i<=m;i++) bz[g[i].c]=g[i].d;
	dfs(1);
	printf("%d\n",ans);
	ans=0;
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%d",&T);
	while(T--) work();
}
