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

typedef long long ll;
const int Maxn=2e5+10,mod=1e9+7;

struct Node {
	int c,d;
}q[Maxn];

int T,n,m,v,ans;

int getxi(int x,int y) {
	int re=(x>>(n-y))&1;
	return re;
}
bool check(int x,int y) {// x ab y xi
	for(int i=1;i<=m;i++) {//one
		if(getxi(y,q[i].c)==0&&q[i].d!=1)return false;
		if(getxi(y,q[i].c)==1&&q[i].d!=2)return false;
	}
	for(int i=1;i<=2*(n-1);i+=2) {//two
		int ai=(x>>(2*(n-1)-i))&1,bi=(x>>(2*(n-1)-i-1))&1;
		for(int j=1;j<n;j++) {
			if(getxi(y,j)==ai&&getxi(y,j+1)!=bi)
				return false;
		}
	}
	return true;
}
int getans() {
	// 0 -> 1 , 1 -> 2
	int s=0;
	for(int i=0;i<(1<<(2*(n-1)));i++) {
		for(int j=0;j<(1<<n);j++) {
			if(check(i,j))s++;
		}
	}
	return ans;
}
bool cmp(Node x,Node y) {
	return x.c<y.c;
}

int main() {
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%d",&T);
	while(T--) {
		scanf("%d%d%d",&n,&m,&v);
		for(int i=1;i<=m;i++)
			scanf("%d%d",&q[i].c,&q[i].d);
		ans=0;
		if(n<=12&&m<=12) {
			ans=getans();
			printf("%d\n",ans);
		} else {
			bool f=false;
			sort(q+1,q+1+n,cmp);
			for(int i=2;i<=m;i++) {
				if(q[i].c==q[i-1].c&&q[i].d!=q[i-1].d) {
					f=true;
					break;
				}	
			}
			if(f) {
				printf("0\n");
				continue;
			} else {
				printf("1\n");
			}
		}
	}

	return 0;
}
/*
3
2 1 2
1 1
2 2 2
1 1
2 2
2 2 2
1 1
1 2
*/

