#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e5+10,M=N*2,inf=0x3f3f3f3f;
const int mod=1e9+7;
int T,n,m,v,ans;
int X[N],a[N],b[N];
struct sat{
	int c,d;
}s[N];
bool cmp(sat x,sat y){return x.c<y.c;}
void dfs(int x){
	if(x==n){
		bool f=1;
//		cout<<"------"<<endl;
//		for(int i=1;i<=n-1;i++){
//			printf("(%d,%d)\n",a[i],b[i]);
//		}cout<<endl;
		for(int i=1;i<=m;i++){
			if(a[s[i].c]==s[i].d){
				int j=1,k=1;
				while(a[s[i].c+j]==b[s[i].c+j-1]&&s[i].c+j<=n){
					if(s[i].c+j==s[i+k].c){
						if(s[i+k].d!=b[s[i].c+j-1]){
							f=0;
							break;
						}else k++;
					}
					j++;
				}
				if(!f) break;
			}
		}
		if(f) ans++;
		return;
	}
	for(int i=1;i<=v;i++){
		for(int j=1;j<=v;j++){
			a[x]=i,b[x]=j;
			dfs(x+1);
		}
	}
}
void solve(){
	scanf("%d%d%d",&n,&m,&v);
	ans=0,memset(s,0,sizeof s);
	for(int i=1;i<=m;i++) scanf("%d%d",&s[i].c,&s[i].d);
	sort(s+1,s+1+m,cmp);
	for(int i=1;i<=m;i++) if(s[i].c==s[i+1].c){puts("0");return;}
	dfs(1);
	printf("%d\n",ans);
}

int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}


