#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+10;

int T,n,m,v;
int pos[maxn];
bool check(int sta,int ass) {
	for(int i=1;i<n;i++) {
		if(pos[i] && (pos[i]-1==(sta>>(i-1)&1))) {
			int to=(ass>>(i-1)&1);
			for(int j=i+1;j<=n;j++) {
				if(pos[j]&& to+1!=pos[j]) return 0;
				if(to!=(sta>>(j-1)&1)) { i=j-1;break; }
				else to=(ass>>(j-1)&1);
			}
		}
	} return 1;
}
void subtask1() {
//	cout<<n<<" "<<m<<" "<<v<<endl;
	int tot=(1<<(n-1))-1;
	ll ans=0;
//	cout<<tot<<endl;
	for(int i=0;i<=tot;i++) {
		for(int j=0;j<=tot;j++) {
//			ans+=check(i,j);
			int tmp=check(i,j);
			ans+=tmp;
//			cout<<i<<" "<<j<<" "<<tmp<<endl;
		}
	} 
	printf("%lld\n",ans);
}
void solve() {
	bool flag=0;
	scanf("%d%d%d",&n,&m,&v);
	for(int i=1;i<=m;i++) {
		int x,y;
		scanf("%d%d",&x,&y);
		if(x<=12) {
			if(!pos[x])pos[x]=y;
			else if(pos[x]!=y) flag=1;
		}
	}
	if(flag) { 
		printf("0\n"); 
		if(n<=12) for(int i=1;i<=n;i++) pos[i]=0;
		return; 
	}
	if(n<=12&&m<=12) {
		subtask1();
		for(int i=1;i<=n;i++) pos[i]=0;
	}
}
int main() {
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}
