#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int re(){
	int a=0;bool f=1;
	char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar())
		if(ch=='-') f=0;
	for(;ch>='0'&&ch<='9';ch=getchar())
		a=(a<<3)+(a<<1)+(ch^48);
	return f? a:-a;
}
const int M=1e5+5;
int n,m,v;
int x[M*100],a[M],c[M],d[M];
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	int T=re();
	while(T--){
		int E=1;
		n=re(),m=re(),v=re();
		for(int i=1;i<=m;++i){
			c[i]=re();d[i]=re();
			if(x[c[i]]) E=0;
			x[c[i]]=d[i];
		}
		for(int i=1;i<n;++i){
			
		}
		if(!E)  cout<<"0\n";
		else cout<<v*v/n<<"\n";
		E=1;
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}
