#include<bits/stdc++.h>
#define ll long long
#define fo(x,a,b) for(register int (x)=(a);(x)<=(b);++(x)) 
#define fr(x,a,b) for(register int (x)=(a);(x)>=(b);--(x)) 
using namespace std;
int n,m,v,c[1000003],d[100003],p[13],vis[13],as;
bool w,x,y,z;
void solvef(){
	if(v==1){
		w=1;
	}else{
		bool e=1,f=1,g=1,h=1;
		fo(i,1,n-1){
			if(p[i]==1&&p[i+1]!=2)
				e=0;
			if(p[i]==2&&p[i+1]!=2)
				f=0;
			if(p[i]==2&&p[i+1]!=1)
				g=0;
			if(p[i]==1&&p[i+1]!=1)
				h=0;
		}
		if(e)w=1;
		if(f)x=1;
		if(g)y=1;
		if(h)z=1;
	}
}
void dfs(int x){
	if(x>n){
		solvef();
		return;
	}
	if(vis[x]) dfs(x+1);
	else{
		fo(i,1,v){
			p[x]=i;
			dfs(x+1);
 		}
	}
}
int main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	ios::sync_with_stdio(false);cin.tie(0);	cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		bool is=0;
		cin>>n>>m>>v;
		fo(i,1,m){
			cin>>c[i]>>d[i];
			if(p[c[i]]){
				if(p[c[i]]!=d[i]){
					cout<<"0\n";
					is=1;
					break;
				}
			}else{
				p[c[i]]=d[i];
			}
			vis[c[i]]=1;
		}
			dfs(0);
			if(w)as++;
			if(x)as++;
			if(y)as++;
			if(z)as++;
			if(!is)cout<<as<<"\n";
			as=0;
			w=0;x=0;y=0;z=0;
			fo(i,1,n) vis[i]=0;
			fo(i,1,n) p[i]=0;
		
	}
	return 0;
}

