#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int cnt,n,T,m,v,ans;
int x[N],a[N],b[N];
bool dfs(int pos){
	if(pos>=3*n-1){
	
		for(int i=1;i<=n-1;i++){
			if(x[i]==a[i]&&x[i+1]!=b[i])
				return 0;
		}

//		cout<<"YEs\n";
		ans++;
		return 1;
	}
	if(pos<n){
		static int ccnt=0;
		for(int i=1;i<=v;i++){
			a[pos]=i;
//			cout<<"asdasfsdfs: "<<++ccnt<<" pos: "<<a[pos]<<endl;
			if(x[pos]==a[pos]&&pos+1<=n){
				if(x[pos+1]){
					b[pos]=x[pos+1];
					dfs(pos+1);
					b[pos]=0;
				}
				else dfs(pos+1);
			}
			else dfs(pos+1);
		}
	}
	if(pos>=n&&pos<2*n-1){
		if(b[pos-n+1])	dfs(pos+1);
		else{
			for(int i=1;i<=v;i++){
				b[pos-n+1]=i;
				dfs(pos+1);
				b[pos-n+1]=0;
			}
		}
	}
	if(pos>=2*n-1&&pos<=3*n-2){
		if(x[pos-2*n+2])	dfs(pos+1);
		else{
			for(int i=1;i<=v;i++){
				x[pos-2*n+2]=i;
				if(dfs(pos+1)){
					x[pos-2*n+2]=0;
					return 1;
				}
				x[pos-2*n+2]=0;	
			}
		}
	}
	
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	cin>>T;
	while(T--){
		ans=0;
		cin>>n>>m>>v;
		bool don=0;
		memset(x,0,sizeof x);
		for(int c,d,i=1;i<=m;i++){
			cin>>c>>d;
			if(x[c]&&x[c]!=d){
				cout<<0<<"\n";
				don=1;
			}
			x[c]=d;
		}
		if(don)	continue;
//		cout<<"x: ";
//		for(int i=1;i<=n;i++) cout<<x[i]<<" ";
//		cout<<endl;
		dfs(1);
		cout<<ans<<endl;
	}
	return 0;
}

