#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long
using namespace std;
ll T,ans=0;
ll n,m,v;
ll a[15];
ll x[15],y[15];
bool check(){
	ll c[15];
	for(ll i=1;i<=n;i++) c[i]=a[i];
	for(ll i=1;i<n;i++){
		if(a[i]){
			if(a[i]==x[i]){
				if(a[i+1]&&a[i+1]!=y[i]) return false;
				a[i+1]=y[i];
			}
		}
	}
	for(ll i=1;i<=n;i++) a[i]=c[i];
	return true;
}
void solve(ll now){
	if(now>=n){
		if(check()) ans++;
		return; 
	}
	for(ll i=1;i<=v;i++){
		for(ll j=1;j<=v;j++){
			x[now]=i,y[now]=j;
			solve(now+1);
		}
	}
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%lld",&T);
	while(T--){
		ans=0;
		memset(a,0,sizeof(a));
		scanf("%lld%lld%lld",&n,&m,&v);
		bool f=false;
		for(ll i=1;i<=m;i++){
			ll id,x;
			cin>>id>>x;
			if(a[id]&&a[id]!=x){
				printf("0\n");
				f=true;
				break;
			}
			a[id]=x;
		}
		if(f==true) continue;
		solve(1);
		printf("%lld\n",ans);
	}
	return 0;
}
