//70
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7,maxn=1e7+25;
ll n,T,m,v,a[maxn];
ll dfs(string s,ll l,ll r){
	if(r-l+1==2){
		if(s[l]=='1'&&s[r]=='1')return v*(v-1);
		return v*v;
	}
	if(s[l]=='0'){
		return v*v*dfs(s,l+1,r);
	}else{
		string y=s;
		ll ansa=(v-1)*v*dfs(s,l+1,r);
		y[l+1]='1';
		ll ansb=dfs(y,l+1,r);
		if(s[l+1]=='0')ansb*=v;
		return ansa+ansb;
	}
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%lld",&T);
	while(T--){
		scanf("%lld%lld%lld",&n,&m,&v);
		for(ll i=1;i<=n;i++)a[i]=0;
		ll ans=1;
		string s;
		for(ll i=1,c,d;i<=m;i++){
			scanf("%lld%lld",&c,&d);
			if(a[c]!=0&&a[c]!=d){
				ans=-1;
			}
			a[c]=d;
		}
		if(ans!=1){
			printf("0\n");
			continue;
		}
		for(ll i=1;i<=n;i++){
			char c='0';
			if(a[i])c++;
			s+=c;
		}
		ans=dfs(s,0,n-1);
		printf("%lld\n",ans);
	}
	return 0;
}
