#include<bits/stdc++.h>
using namespace std;
long long t,n,m,v,c[10001000],d[10001000],o[10000010],ans,a,b,x=10000010,kl,cnt;
int so(long long a1,long long i){
	cout<<a1<<" "<<i<<endl;
	if(i==n){
		if(o[i]!=0){
			if(a1!=o[i]){
				return 0;
			}
		}
		ans+=v;
		return 0;
	}
	if(i>n||a1>v||i<1||a1<1){
		return 0;
	}
	if(o[i]!=0){
		if(a1!=o[i]){
			return 0;
		}
	}
	for(long long b2=1;b2<=v;b2++){
		so(b2,i+1);
	}
	return 0;
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	cin>>t;
	for(long long q=1;q<=t;q++){
		ans=0,kl=0;
		memset(c,0,x);
		memset(d,0,x);
		memset(o,0,x);
		cin>>n>>m>>v;
		for(long long i=1;i<=m;i++){
			cin>>c[i]>>d[i];
			o[c[i]]=d[i];
		}
		for(long long a1=1;a1<=v;a1++){
			so(a1,1);
		}
	cout<<ans<<"\n";
}
	return 0;
}
