#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int M=1e9+7;
int T,n,m,v;
int a[N],b[N],c[N],d[N],x[N],ans;
void dfs1(int k){
	if(k>n){
		bool f=true;
		for(int i=1;i<n;i++)
			if(x[i]==a[i]&&x[i+1]!=b[i]){
				f=false;
				break;
			} 
		if(f) ans++;
		return;	
	}
	if(x[k]) dfs1(k+1);
	else{
		x[k]=1;
		dfs1(k+1);
		x[k]=2;
		dfs1(k+1);
	} 
}
void dfs(int k){
	if(k>n-1){
		dfs1(1); 
		return;
	}
	a[k]=1,b[k]=1;
	dfs(k+1);
	a[k]=1,b[k]=2;
	dfs(k+1);
	a[k]=2,b[k]=1;
	dfs(k+1);
	a[k]=2,b[k]=2;
	dfs(k+1); 
}
void work1(){
	dfs(1);
	cout<<ans<<"\n";
} 
int 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--){
		ans=0;
		cin>>n>>m>>v;
		for(int i=1;i<=n;i++) x[i]=0;
		bool fl=false;
		for(int i=1;i<=m;i++){
			cin>>c[i]>>d[i];
			if(x[c[i]]){
				fl=true;
				break;
			}
			x[c[i]]=d[i];
		}
		if(fl){
			cout<<0<<"\n";
			continue;
		}
		if(v<=2) work1();
		else cout<<0<<"\n";
	} 
	return 0;
}
/*
3
2 1 2
1 1
2 2 2
1 1 
2 2
2 2 2
1 1 
1 2
*/
