#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,mod=1e9+7;
int T,n,m,v,c[N],d[N],a[N],b[N];
map<int,int> mp;
namespace sub1
{
	int ans;
	void dfs(int k)
	{
		if(k==n)
		{
			for(int i=1;i<=m;i++)
				if(c[i]!=1&&b[c[i]-1]!=d[i]) return;
			return ans++,void();
		}
		for(int i=1;i<=v;i++)
			for(int j=1;j<=v;j++)
			{
				a[k]=i,b[k]=j;
				dfs(k+1);
				a[k]=b[k]=0;
			}
	}
	void solve()
	{
		ans=0;
		dfs(1);
		printf("%d\n",ans);
	} 
}
void mian()
{
	scanf("%d%d%d",&n,&m,&v);
	mp.clear();
	bool flag=false;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&c[i],&d[i]);
		if(mp[c[i]]) flag=true;
			else mp[c[i]]=1;
	}
	if(flag) return puts("0"),void();
	if(n<=12) return sub1::solve(),void();
	puts("0");
}
int main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%d",&T);
	while(T--) mian();
	return 0;
}
