#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5,mod=1e9+7;
int t,n,m,v,d[N];
bool b;
struct node{
	int x,y;
}a[N];
bool cmp(node a,node b){
	return a.x<b.x;
}
bool check(int now){
	int last=now&1;
	for(int i=2;i<=n;++i){
		if(d[i-1]==last+1&&d[i]&&d[i]!=((bool)(now&(1<<i-1))+1)) return false;
		last=now&(1<<i-1);
	}return true;
}
void f(){
	memset(d,0,sizeof(d));
	for(int i=1;i<=m;++i) d[a[i].x]=a[i].y;
	int maxx=1<<n,res=0;
	for(int i=0;i<maxx;++i){
		if(check(i)) ++res;
	}cout<<res<<'\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--){
		b=false;
		cin>>n>>m>>v;
		for(int i=1;i<=m;++i) cin>>a[i].x>>a[i].y;
		sort(a+1,a+1+m,cmp);
		for(int i=1;i<=m;++i){
			if(a[i].x==a[i-1].x&&a[i].y!=a[i-1].y){
				b=true;
				break;
			}
		}
		if(!b){
			if(n==1) cout<<"0\n";
			else if(n<=20) f();
			else cout<<"0\n";
		}
		else cout<<"0\n";
	}
	return 0;
} 
