#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
int x[1000010],c[100010];
int a(int x,int zwc)
{
	int k=1;
	for(int i=1;i<=x;i++)
	k*=zwc;
	return k;
}
int main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	long long T,m,n,v,ans=0,num=0;
	cin>>T;
	while(T--)
	{
	
		num=0;
		memset(x,0,sizeof(x));
		cin>>n>>m>>v;
		for(int i=1;i<=m;i++)
		{
			cin>>c[i];
			cin>>x[c[i]];
		}
		if(num==1)continue;
		ans=a(m-1,3)+a(n-m,4);
		cout<<ans-1<<endl;
	}
	return 0;
}
