#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+5,mod=1e9+7;
int n,m,v,z[N],ans,a[N],b[N];
void dfs(int x){
	if (x==n){
		int tmp=0;
		for (int i=1;i<n;i++){
			if (z[i]){
				if (!tmp){
					tmp=z[i];
				}
				else {
					if (tmp!=z[i]) return ;
				}
			}
			if (!tmp) continue ;
			if (tmp==a[i]) tmp=b[i];
			else tmp=0;
		}
		if (tmp&&z[n]&&z[n]!=tmp) return ;
		//cout<<a[1]<<" "<<b[1]<<endl;
		ans++;return ;
	}
	for (int i=1;i<=v;i++){
		for (int j=1;j<=v;j++){
			a[x]=i,b[x]=j;
			dfs(x+1);
		}
	}
}
void work(){
	memset(z,0,sizeof(z));
	cin>>n>>m>>v;bool f=0;ans=0;
	for (int i=1;i<=m;i++){
		int c,d;cin>>c>>d;
		if (z[c]){
			f=1;continue ;
		}z[c]=d;
	}if (f||n>12) return cout<<0<<endl,void();
	dfs(1);cout<<ans<<endl;
}
signed main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	ios::sync_with_stdio(0);
	int t;cin>>t;while (t--) work();
	return 0;
}
