#include<bits/stdc++.h>
using namespace std;
long long T;
long long x,y;
long long n,m,v;
struct yy
{
	long long c,d;
}a[100010];
long long X[4100][15];
long long cnt,answer;
void build(long long ans,long long x)
{
	long long op=n;
	for(int i=1;i<=n;i++)X[ans][i]=1; 
	while(x)
	{
		if(x%2==1)X[ans][op]=2;
		else X[ans][op]=1;
		op--;
		x>>=1;
	}
	for(int i=1;i<=m;i++)
	{
		X[ans][a[i].c]=a[i].d;
	}
	return;
}
int zk[15],tys[15];
bool check()
{
	for(int i=1;i<=1<<n;i++)
	{
		for(int j=1;j<n;j++)
		{
			bool zk_ak=0;
			for(int k=1;k<n;k++)
			{
				if(X[i][j]==zk[k]&&X[i][j+1]!=tys[k])
				{
					zk_ak=1;
					break;
				}
			 } 
			if(zk_ak==0)return true;
		} 
	}
	return false;
}
void init()
{
	for(int i=1;i<=n-1;i++)zk[i]=1;
	return;
}
void init2()
{
	for(int i=1;i<=n-1;i++)tys[i]=1;
	return;
}
void build2(long long x)
{
	long long ccnt=n-1;
	init();
	while(x)
	{
		if(x%2==1)zk[ccnt]=2;
		else zk[ccnt]=1;
		ccnt--;
		x>>=1;
	}
	for(int i=0;i<=(1<<(n-1))-1;i++)
	{
		init2();
		long long op=i;
		long long ui=n-1;
		while(op)
		{
			if(op&1)tys[ui]=2;
			else tys[ui]=1;
			ui--;
			op>>=1;
		}
		if(check()==true)
		{
			
			answer++;
		}
	}
	return;
}
int main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%lld",&T);
	while(T--)
	{
		scanf("%lld%lld%lld",&n,&m,&v);
		cnt=0;
		for(int i=1;i<=m;i++)
		{
			cin>>a[i].c>>a[i].d;
		}
		answer=0;
		for(int i=1;i<=m;i++)
		{
			if(X[0][a[i].c]!=a[i].d&&X[0][a[i].c]!=0)
			{
				answer=-1;
				break;
			}
			X[0][a[i].c]=a[i].d;
		}
		if(answer==-1)
		{
			cout<<0<<"\n";
			continue;
		}
		for(int i=0;i<=(1<<n)-1;i++)
		{
			cnt++;
			build(cnt,i);	
		}
		for(int i=0;i<=(1<<(n-1))-1;i++)
		{
			build2(i);
		}
		printf("%lld\n",answer);
		answer=0;
	}
	return 0;
}
