#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX=0x3f3f3f3f;
const int MAXN=1e6+10;
const int Mod=1e9+7;
inline ll read(){ll x=0,f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}

int x[MAXN],y[MAXN],a[MAXN],vis[MAXN];
int T,n,m,v,f,f1,p,c,ans;

bool check(){
	for(int i=1;i<=n;i++){
		if(a[i]&&a[i+1]&&a[i]==x[i]&&a[i+1]!=y[i])return false;
	} 
	return true;
}
void find(int q){
	if(q==2*n-1){
		if(check())ans++;
		return ;
	}
	for(int i=1;i<=v;i++){
		if(q>n-1)y[q-n+1]=i;
		else x[q]=i;
		find(q+1); 
	}
}
void work(){
	cin>>n>>m>>v;
	ans=0;
	memset(vis,0,sizeof(vis));
	memset(a,0,sizeof(a));
	int f=1;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		a[u]=v;
		if(vis[u])f=0;
		vis[u]=1;
	}
	if(!f)cout<<0<<endl;
	else{
		find(1);
		cout<<ans<<endl;
	}
}

int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	
	cin>>T;
	while(T--){
//		cout<<T<<" ";
		work();
	}
	
	fclose(stdin);
	fclose(stdout);
	return 0;
} 
/*
3
2 1 2 
1 1
2 2 2
1 1
2 2
2 2 2
1 1 
1 2
*/
