#include<iostream>
#include<stdio.h>
using namespace std;
const int N=1e5+10;
int n,m,v;
int a,b,e[N],c[N],d[N];
bool flag;
void dfs(int x)
{
	if(x==n+1)
	{
		
		for(int i=1;i<n;i++)
			if(e[i]==a&&e[i+1]!=b)
				return;
		for(int i=0;i<m;i++)
			if(e[c[i]]!=d[i])
				return;
		flag=1;
		return;
	}
	e[x]=1;
	dfs(x+1);
	e[x]=2;
	dfs(x+1);
}
int main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	int T;
	cin>>T;
	while(T--)
	{
		int ans=0;
		cin>>n>>m>>v;
		for(int i=0;i<m;i++) cin>>c[i]>>d[i];
		for(int i=1;i<=v;i++)
			for(int j=1;j<=v;j++)
			{
				flag=0;
				a=i,b=j;
				dfs(0);
				if(flag) ans++;
			}
		cout<<ans<<endl;
	}
	return 0;
}
