#include <bits/stdc++.h>
using namespace std;

const int MAXN=1e5+7;
int n,m,v,ans,t;
int c[MAXN],d[MAXN],a[MAXN],b[MAXN],x[MAXN];

bool check(){
	/*
	cout<<"ts"<<endl;
	for(int i=1;i<=n;i++) cout<<x[i]<<" ";
	cout<<endl; 
	for(int i=1;i<n;i++) cout<<a[i]<<" ";
	cout<<endl;
	for(int i=1;i<n;i++) cout<<b[i]<<" ";
	cout<<endl<<endl;
	*/
	for(int i=1;i<n;i++){
		if(x[i]==a[i]&&x[i+1]!=b[i]) return false;
	}
	for(int i=1;i<=m;i++){
		if(x[c[i]]!=d[i]) return false;
	}
	return true;
}

bool dfs3(int p){
	if(p==n+1){
		if(check()){
			ans++;
			return true;
		}
		return false;
	}
	for(int i=1;i<=v;i++){
		x[p]=i;
		if(dfs3(p+1)) return true;
	}
	return false;
}

void dfs2(int p){
	if(p==n){
		dfs3(1);
		return;
	}
	for(int i=1;i<=v;i++){
		b[p]=i;
		dfs2(p+1);
	}
}

void dfs1(int p){
	if(p==n){
		dfs2(1);
		return;
	}
	for(int i=1;i<=v;i++){
		a[p]=i;
		dfs1(p+1);
	}
}

int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	while(t--){
		ans=0;
		cin>>n>>m>>v;
		for(int i=1;i<=m;i++){
			cin>>c[i]>>d[i];
		}
		if(v<=2) dfs1(1);
		cout<<ans<<endl;
	}
	return 0;
} 
