#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;
int t,n,m,v,ans,s[50];
void dfs(int p)
{
	if(p==n)
	{
		ans++;
		return;
	}
	for(int i=1;i<=v;i++)
	{
		if(i==s[i])
		{
			for(int j=1;j<=v;j++)
			{
				if(s[p+1]&&s[p+1]!=j) continue;
				int t=s[p+1];
				s[p+1]=j;
				dfs(p+1);
				s[p+1]=t;
			}
		}
		else for(int j=1;j<=v;j++) dfs(p+1);
	}
}
signed main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%lld",&t);
	while(t--)
	{
		bool flag=0;
		memset(s,0,sizeof(s));
		scanf("%lld%lld%lld",&n,&m,&v);
		for(int i=1;i<=m;i++)
		{
			int x,y;
			scanf("%lld%lld",&x,&y);
			if(s[x]&&s[x]!=y) flag=1;
			else s[x]=y;
		}
		if(flag) printf("0\n");
		else
		{
			dfs(1);
			printf("%lld\n",ans);
			ans=0;
		}
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}
