#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,v,T,c[100010],d[100010],a[100010],b[100010];
bool cuo;
long long int ans;

int p[1000010];
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%d",&T);
	for(int q=1;q<=T;q++){
		cuo=false;
		scanf("%d%d%d",&n,&m,&v);
		for(int i=1;i<=n+1;i++){
			p[i]=-1;
			a[i]=1;
			b[i]=1;
		}
		for(int i=1;i<=m;i++){
			scanf("%d%d",&c[i],&d[i]);
			if(p[c[i]]!=-1){
				cuo=true;
				break;
			}
			p[c[i]]=d[i];
		}
		if(cuo){
		}
		else if(v<=2){
			for(;;){
				bool infer=true;
				for(int j=1;j<n;j++){
					if(p[j]==a[j]){
						if(p[j+1]!=-1&&p[j+1]!=b[j]){
							infer=false;
							break;
						}
					}
				}
				if(infer==true){
					ans++;
				}
				//¸ü¸Äa,b
				a[1]++;
				for(int i=1;i<n-1;i++){
					if(a[i]>v){
						a[i]=1;
						a[i+1]++;
					}
				} 
				if(a[n-1]>v){
					a[n-1]=1;
					b[1]++;
				}
				for(int i=1;i<n-1;i++){
					if(b[i]>v){
						b[i]=1;
						b[i+1]++;
					}
				}
				if(b[n-1]>v){
					break;
				}
			}
		}
		cout<<ans<<'\n';
		memset(c,0,sizeof(0));
		memset(d,0,sizeof(0));
		memset(a,0,sizeof(0));
		memset(b,0,sizeof(0));
		ans=0;
		
	} 
	return 0;
}
