#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int t,x[101000];
int n,m,v,sum;
inline void dfs(int dep,int y){
	if(dep==n+1){
		sum++;
		return;
	}
	for(int i=1;i<=v;i=-~i){
		for(int j=1;j<=v;j=-~j){
			if((x[dep]==i&&x[dep+1]==j))continue;
			dfs(dep+1,i);
		}
	}
	
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%d",&t);
	while(t--){
		int p=0;
		sum=0;
		memset(x,0,sizeof(x));
		scanf("%d%d%d",&n,&m,&v);
		for(int i=1;i<=m;i=-~i){
			int c,d;
			cin>>c>>d;
			if(!x[c])
			x[c]=d;
			else{
				if(x[c]!=d)
				p=1;
			}
		}
		if(p==1){
			cout<<-1<<endl;
			continue;
		}
		dfs(1,0);
		cout<<sum/v/v<<endl;
	}
}
