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

long long T;
long long n,m,v;
long long a[100005];
long long usera[100005];
long long userb[100005];
long long sum=0,cnt;
long long visa[100005];
long long visb[100005];

void check(){
	long long flag=1;
	for(int i=1;i<=n;i++){
//		cout<<i<<" "<<a[i]<<" "<<usera[i]<<"\n"<< a[i+1]<<" "<<userb[i]<<"\n\n";
		if((a[i]==usera[i] && a[i]!=0) || a[i]==0){
			
			if((a[i+1]==userb[i] && a[i+1]!=0) || a[i+1]==0){
		//		cout<<"111\n";
				continue;	
			}
			else{
		//		cout<<">>>\n";
				flag=0; break;
			}
			
		}
	}
//	cout<<flag<<"flag\n";
	if(flag==1){
		cnt++;
	}
	return;
}

void dfsb(long long place,long long val){
//	cout<<place<<" "<<val<<"\n";
	if(place==n+1){
		
/*		for(int i=1;i<=n;i++){
			cout<<usera[i]<<" ";
		}cout<<"\n";
		for(int i=1;i<=n;i++){
			cout<<userb[i]<<" ";
		}cout<<"\n\n";	
*/		
		check();
		return;	
	}
	userb[place]=val;
	for(int i=1;i<=v;i++){
		if(place==n && i>1) break;
		dfsb(place+1,i);
	}
}

void dfs(long long place,long long val){
//	if(visa[place]) return;
//	cout<<place<<" "<<val<<"\n";
	if(place==n+1){
//		for(int i=1;i<=n;i++){
//			cout<<usera[i]<<" ";
//		}cout<<"\n";
	//	cout<<place<<" "<<val<<"\n";
		for(int i=1;i<=v;i++) dfsb(1,i);
		return;
	}
	usera[place]=val; visa[place]=1;
	for(int i=1;i<=v;i++){
		if(place==n && i>1) break;
		dfs(place+1,i);
	}
	return;
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	cin>>T;
	while(T--){
		scanf("%lld %lld %lld",&n,&m,&v);
		long long flag=0,sum=0;
		for(int i=1;i<=m;i++){
			long long c,d; scanf("%lld %lld",&c,&d);
			if(a[c]!=0 && a[c]!=d){
				flag=1;
			}			
			a[c]=d;
		}		
		if(flag==1){
			printf("0\n"); continue;
		}
		for(int i=1;i<=v;i++) 
		dfs(1,i);
		printf("%lld\n",cnt/n/n);
	}
/*
3
2 1 2
1 1	
*/
	
	return 0;
} 
