#include <bits/stdc++.h>
using namespace std ;
const int N = 1e5+10 ;
int aa[10] = {0,1,1,2,2};
int bb[10] = {0,1,2,1,2} ; 
int kkk[15][10] ;  
int tt[10] ; 
int sum[10] ;
int n , m ,v;
int sz[20] ; 
int mb[10] ; 
struct edge{
	int cj,dj ; 
}g[N];
int ans = 0 ;
void dfs(int s ){
	if(s == n+1 ){
		for(int i = 1 ; i <= 4 ; i++){
			int flag = 1;
			for(int j = 1 ; j < n ; j++){
				if(mb[j] == aa[i]){
					if(mb[j+1] == bb[i]){
						if(!kkk[j][i]){
//							cout <<aa[i]<<" "<<bb[i]<<endl;
							kkk[j][i] = 1;
							kkk[j][0]++ ; 
						}
					}
				}
				else{
				if(!kkk[j][i]){
//							cout <<aa[i]<<" "<<bb[i]<<endl;
							kkk[j][i] = 1;
							kkk[j][0]++ ; 
						}
					}
			}
		}
	}
	

	else{
		if(mb[s]){
			dfs(s+1) ; 
		}
		else{
			mb[s] = 1 ; 
			dfs(s+1) ; 
			mb[s] = 2 ; 
			dfs(s+1) ;
		}
	}
}
int main(){
	freopen("assign.in","r",stdin) ; 
	freopen("assign.out","w",stdout) ;
	
	int t;
	cin >> t;
	while(t--){
		cin >> n >> m >> v ;
		for(int i = 1 ; i <= m ; i++){
			cin >> g[i].cj >> g[i].dj ;
			if(tt[g[i].cj] && g[i].cj != g[i].dj){
				ans = 0 ;
				v = 0 ;
				break;
			}
			if(!tt[g[i].cj]){
				tt[g[i].cj] = 1;
			}
		}
		if(v==2){
			for(int i = 1 ; i<= m ; i++){
				mb[g[i].cj] = g[i].dj ; 
			}
//			cout<<"AAAa" ;
			dfs(1) ; 
		}
		long long ans = 1;
		for(int i = 1; i <n ; i++){
			ans *= kkk[i][0] ; 
//			cout << kkk[i][0]<<endl;
		}
		cout <<ans <<endl;
		memset(mb , 0 ,sizeof mb) ; 
		memset(sum , 0,sizeof sum) ; 
		memset(tt,0,sizeof tt) ; 
		memset(kkk,0,sizeof kkk);
		ans= 0 ;
	} 
	
	
	
	return 0;
} 
