#include<bits/stdc++.h>
using namespace std;
const int N=13;
int n,A[N],m,v,c[N],d[N],ans,num[2*N],a[N];
int check(){
	for(int i=1;i<=n;i++)a[i]=A[i];
	for(int i=1;i<n;i++)c[i]=num[i];
	for(int i=1;i<n;i++)d[i]=num[i+n-1];
//	for(int i=1;i<n;i++)cout<<c[i]<<' ';
//	cout<<endl;
//	for(int i=1;i<n;i++)cout<<d[i]<<' ';
//	cout<<"\n------------\n";
	for(int i=1;i<n;i++){
		if(a[i]==c[i]){
			if(a[i+1]==0){
				a[i+1]=d[i]; 
			}
			else {
				if(a[i+1]!=d[i])return 0;
			}
		}
	}
	return 1;
}
void dfs(int t,int val){
	if(t>2*(n-1)){
		ans+=check();
//		cout<<'\n'<<check()<<'\n';
//			for(int i=1;i<n;i++)cout<<c[i]<<' ';
//	cout<<endl;
//	for(int i=1;i<n;i++)cout<<d[i]<<' ';
//	
//	cout<<"\n------------\n";
		return;
	}
	num[t]=val;
	dfs(t+1,1);
	dfs(t+1,2);
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	int T;
	cin>>T;
	while(T--){
		ans=0;
		scanf("%d%d%d",&n,&m,&v);
		memset(num,0,sizeof(num));
		memset(A,0,sizeof(a));
		memset(d,0,sizeof(d));
		memset(c,0,sizeof(c));
		bool flag=0;
		for(int i=1;i<=m;i++){
			int x,y;
			scanf("%d%d",&x,&y);
			if(A[x]!=0){
				flag=1;
			}
			A[x]=y;
		}
		if(flag)printf("0\n");
		else{
			dfs(1,1);
			if(v==2)dfs(1,2);
			printf("%d\n",ans/2);	
		}
	
	} 
	
}
