#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
long long ans=0;
bool flag=1;
int n,m,v;
int a[100005];
int ta[100005],tb[100005];
bool pan(){
	for(int i=1;i<n;i++){
		if(a[i]!=0&&a[i+1]!=0){
			if(a[i]==ta[i]&&a[i+1]!=tb[i]){
				return 0;
			}
		}
	}
	return 1;
}
void dfs(int p){
	if(p==n){
		if(pan())ans++;
		return;
	}
	for(int i=1;i<=v;i++){
		for(int j=1;j<=v;j++){
			ta[p]=i;tb[p]=j;
			dfs(p+1);
		}
	}
}
int main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int t;cin>>t;
	while(t--){
		ans=0;flag=1;
		memset(a,0,sizeof(a));
		cin>>n>>m>>v;
		for(int i=1;i<=m;i++){
			int c,d;
			cin>>c>>d;
			if(a[c]!=0)flag=0;
			a[c]=d;
		}if(v<=2){
			dfs(1);
		}
		if(!flag)ans=0;
		cout<<ans<<endl;
	}
}
//ƭ 
