#include<bits/stdc++.h>
#define ll int
#define N 55
#define M 2555
using namespace std;
inline char nc(){
	static char buf[1000000],*p=buf,*q=buf;
	return p==q&&(q=(p=buf)+fread(buf,1,1000000,stdin),p==q)?EOF:*p++;
}
inline ll read(){
	ll res = 0;
	char c = nc();
	while(c<'0'||c>'9')c=nc();
	while(c<='9'&&c>='0')res=res*10+c-'0',c=nc();
	return res;
}
char obuf[1<<21],*p3=obuf; 
inline void pc(char c){ 
	p3-obuf<=(1<<20)?(*p3++=c):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=c); 
} 
inline void write(long long x){ 
	if(x<0) pc('-'),x=-x; 
	if(x>9) write(x/10); 
	pc(x%10+'0'); 
}
ll T,n,m,i,x[M],y[M],maps[N][N],n1,n2,p1[N],p2[N],que[N],head,tail,vis1[M],vis2[M],used[M],mk[M],sta[M],top;
long long val1[N],val2[N],non_vis,alls;
inline void bfs1(){
	n1 = 0,que[head=1] = 1,tail = 1,non_vis = alls-(1ll<<1);
	while(head<=tail){
		p1[++n1] = que[head++];
		long long val = (val1[p1[n1]]&non_vis);
		while(val){
			ll pos = __builtin_ctzll(val);
			vis1[maps[p1[n1]][pos]] = 1,que[++tail] = pos;
			val -= (1ll<<pos),non_vis -= (1ll<<pos);
		}
	}
}
inline void bfs2(){
	n2 = 0,que[head=1] = 1,tail = 1,non_vis = alls-(1ll<<1);
	while(head<=tail){
		p2[++n2] = que[head++];
		long long val = (val2[p2[n2]]&non_vis);
		while(val){
			ll pos = __builtin_ctzll(val);
			vis2[maps[pos][p2[n2]]] = 1,que[++tail] = pos;
			val -= (1ll<<pos),non_vis -= (1ll<<pos);
		}
	}
}
inline void del(ll id){
	used[id] = 1,maps[x[id]][y[id]] = 0,val1[x[id]] -= (1ll<<y[id]),val2[y[id]] -= (1ll<<x[id]);
}
inline void add(ll id){
	used[id] = 0,maps[x[id]][y[id]] = id,val1[x[id]] += (1ll<<y[id]),val2[y[id]] += (1ll<<x[id]);
}
inline long long dfs(ll x){
	if(x==0){
		bfs1(),bfs2();
		if(n1==n&&n2==n) return 1;
		return 0;
	}
	for(ll i=1;i<=m;i++) vis1[i]=0,vis2[i]=0;
	bfs1(),bfs2();
	vector<ll> viss(m+1),cntt(m+1),used2(m+1),mk2(m+1);
	for(ll i=0;i<=m;i++) viss[i]=cntt[i]=used2[i]=mk2[i]=0;
	for(ll i=1;i<=m;i++) viss[i]=(vis1[i]|vis2[i]),used2[i]=used[i],mk2[i]=mk[i];
	long long ans = 0;
//	cout<<"!!! "<<sta[1]<<" "<<sta[2]<<" "<<sta[3]<<endl;
//	cout<<x<<endl;
//	for(ll i=1;i<=m;i++) cout<<vis1[i]<<" ";
//	cout<<endl;
//	for(ll i=1;i<=m;i++) cout<<vis2[i]<<" ";
//	cout<<endl;
	if(n1==n&&n2==n){
		for(ll i=1;i<=m;i++) if(!viss[i]&&!used2[i]&&!mk2[i]) cntt[i]++;
		for(ll i=1;i<=m;i++) cntt[i]+=cntt[i-1];
		if(x==1) ans+=cntt[m];
		if(x==2) ans+=1ll*cntt[m]*(cntt[m]-1)/2;
		if(x==3) ans+=1ll*cntt[m]*(cntt[m]-1)*(cntt[m]-2)/6;
		for(ll i=1;i<=m;i++) if(viss[i]&&!used2[i]) mk[i]++;
		for(ll i=m;i>=1;i--){
			if(viss[i]&&!used2[i]&&!mk2[i]){
				sta[++top] = i;	
				del(i);		
				ans += dfs(x-1);
				add(i);
				top--;				
			}
			if(viss[i]&&!used2[i]) mk[i]--;
		}
	}
	return ans;
}
inline void solve(){
	n=read(),m=read();
	alls = 0;
	for(i=1;i<=n;i++) alls|=(1ll<<i);
	for(i=1;i<=m;i++) x[i]=read(),y[i]=read(),maps[x[i]][y[i]]=i,val1[x[i]]|=(1ll<<y[i]),val2[y[i]]|=(1ll<<x[i]);
	write(1ll*m*(m-1)*(m-2)/6-dfs(3)),pc('\n');
}
inline void clear(){
	memset(maps,0,sizeof(maps));
	memset(x,0,sizeof(x));
	memset(y,0,sizeof(y));
	memset(val1,0,sizeof(val1));
	memset(val2,0,sizeof(val2));
}
int main(){
	T=read();
	while(T--) solve(),clear();
	return fwrite(obuf,p3-obuf,1,stdout),0;
}