#include<bits/stdc++.h>
#define LL long long
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
#define repn(i,a,b,g) for(LL i=a;i<b;i+=g)
using namespace std;
LL n,m,k,a[100010],b[100010],u,v,cnt[100010],su;
pair<LL,LL>f[100010];
void dfs(LL no)
{
	if(no==n)
	{
		rep(i,1,n,1)
		{
			b[i]=a[i];
		}
		repn(i,1,n,1)
		{
			if(b[i]==f[i].first)
			{
				if(b[i+1]&&b[i+1]!=f[i].second)return;
				b[i+1]=f[i].second;
			}
		}
		su++;
		return;
	}
	rep(i,1,k,1)
	{
		rep(j,1,k,1)
		{
			f[no]=make_pair(i,j);
			dfs(no+1);
		}
	}
}
void sol()
{
	scanf("%lld%lld%lld",&n,&m,&k);
	rep(i,1,n,1)
	{
		a[i]=0;
		cnt[i]=0;
	}
	rep(i,1,m,1)
	{
		cin>>u>>v;
		if(cnt[u]&&cnt[u]!=v)
		{
			puts("0");
			return;
		}
		a[u]=v;
		cnt[u]=v;
	}
	su=0;
	dfs(1);
	printf("%lld\n",su);
}
int main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	LL T;
	scanf("%lld",&T);
	while(T--)
	{
		sol();
	}
	return 0;
}
/*
10:56 maybe can pian 25 pts, see next timu first
11:01 try baoli
11:26 done,25 pts get,now 125,try T4
*/
/*
i still continue to study OI because of MST(luogu 815497) encouraged me last year when i got low pts
but this year she can't come to NOIP
so MST, if you see this in daimamihuoxingwei, it's my courage to you, you can still go on
*/
