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

int c[100010];
int MAX=1e9+7;

int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	int t;
	cin>>t;
	while(t--){
		memset(c,0,sizeof(c));
		int n,m,v,flag=1,dyx=0;
		cin>>n>>m>>v;
		for(int i=1;i<=m;i++){
			int a,b;
			cin>>a>>b;
			if(c[a]&&c[a]!=b){
				cout<<0<<'\n';
				flag=0;
				break;
			}else{
				c[a]=b;
			}
		}
		for(int i=1;i<=n;i++){
			if(c[i]){
				dyx++;
			}
		}
		if(flag)cout<<(pow(3,max(dyx-1,0))*pow(4,n-dyx))<<'\n';
	}
	return 0;
}
