#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second

const int N=122;
int T,n,m,v;
pii u[N];
int a[N],b[N];
int ans;
bool chk(int x)
{
	if(x>n)
	{
		for(int i=1;i<n;i++)
			if(b[i]==u[i].fi&&b[i+1]!=u[i].se)
				return false;
		return true;
	}
	if(a[x])
		return b[x]=a[x],chk(x+1);
	int ret=0;
	for(int i=1;i<=v;i++)
	{
		b[x]=i;
		if(chk(x+1))
			return true;		
	}
	return false;
}
void dfs(int x)
{
	if(x>n-1)
	{
//		for(int i=1;i<n;i++)
//			cout<<u[i].fi<<'*'<<u[i].se<<endl;
//		cout<<endl;
		if(chk(1))
			++ans;
		return;
	}
	for(int i=1;i<=v;i++)
		for(int j=1;j<=v;j++)
			u[x]={i,j},dfs(x+1);
}
signed main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--)
	{
		cin>>n>>m>>v;
		memset(a,0,sizeof(a));
		ans=0;
		bool ok=1;
		for(int i=1;i<=m;i++)
		{
			int c,d;
			cin>>c>>d;
			if(a[c]!=d&&a[c])
				ok=0;
			a[c]=d;
		}
		dfs(1);
		if(ok)
			cout<<ans<<endl;
		else
			cout<<0<<endl;
	}
	return 0;
}
