#include<bits/stdc++.h>
using namespace std;
long long sss,dsds,ks,bz[4][10007],js1[4],T,a1,a2,ans,ss,n,m,k,l,k1[3007],k2[3007],k3[3007],k4[3007],bs[4][10007],js[4],cd,kk1[3007],kk2[3007],ccd;
long long bi,br[53],bw[53];
bool b1[1007];
int bj[10007],sj[10007];
void DD(int x,int y){
	k1[++cd]=k2[x];
	k2[x]=cd;
	k3[cd]=y;
	k4[cd]=x;
	br[x]^=(1ll<<(y-1));
}
void DDD(int x,int y){
	kk1[++ccd]=kk2[x];
	kk2[x]=ccd;
	bw[x]^=(1ll<<(y-1));
}
void ka1(int x,int y,int z){
	b1[y]=1;
	for(int j=k2[y];j;j=k1[j]){
		int tt=k3[j];
		if(!b1[tt]&&sj[j]!=-1){
			ka1(y,tt,z);
			if(!bj[j])bs[z][++js[z]]=j;
			bj[j]=1;
		}
	}
}
void ka2(int x,int y){
	bi^=(1ll<<(y-1));
	long long s=bi&br[y];
	while(s){
		long long tt=__builtin_ctzll(s)+1;
		ka2(y,tt);
		s&=bi;
		if((s>>(tt-1))&1)s^=(1ll<<(tt-1));
	}
}
void bl(int z){
	if(z==0){
	    bi=(1ll<<n)-1;
	    if(br[1]==30)sss++;
		ka2(0,1);
		if(bi!=0)return;
		swap(br,bw);
		bi=(1ll<<n)-1;
		ka2(0,1);
		swap(br,bw);
		if(bi!=0)return;
		ans++;
        return;
	}
	js[z]=0;for(int i=1;i<=m;i++)bj[i]=0;for(int i=1;i<=n;i++)b1[i]=0;
	ka1(0,1,z);for(int i=1;i<=cd;i++)swap(k1[i],kk1[i]),swap(k3[i],k4[i]);
	for(int i=1;i<=n;i++)swap(k2[i],kk2[i]);
	for(int i=1;i<=n;i++){
		if(b1[i]==0){
	        for(int i=1;i<=cd;i++)swap(k1[i],kk1[i]),swap(k3[i],k4[i]);
	        for(int i=1;i<=n;i++)swap(k2[i],kk2[i]);
			return;
		}
		else b1[i]=0;
	}
	ka1(0,1,z);for(int i=1;i<=cd;i++)swap(k1[i],kk1[i]),swap(k3[i],k4[i]);
	for(int i=1;i<=n;i++)swap(k2[i],kk2[i]);
	for(int i=1;i<=n;i++){
		if(b1[i]==0)return;
		else b1[i]=0;
	}
	for(int i=1;i<=js[z];i++){
		int j=bs[z][i];
		bj[j]=0;
		if(sj[j]==0){
			sj[j]=-1;ss--;
		    br[k4[j]]^=(1ll<<(k3[j]-1));
		    bw[k3[j]]^=(1ll<<(k4[j]-1));
		    bl(z-1);
		    br[k4[j]]^=(1ll<<(k3[j]-1));
		    bw[k3[j]]^=(1ll<<(k4[j]-1));
		    sj[j]=1;
		    ks++;
		    bz[z][++js1[z]]=j;
		}
	}
	for(int i=1;i<=js1[z];i++){
		sj[bz[z][i]]=0;
		ss++;ks--;
	}
	for(int i=1;i<=js[z];i++)if(sj[bs[z][i]]==1)ss++;
	js1[z]=0;
	ss-=js[z];
	if(z==3)ans+=1ll*ss*(ss-1)/2*(ss-2)/3;
	if(z==2)ans+=ss*(ss-1)/2;
	if(z==1)ans+=ss;
	ss+=js[z];
	for(int i=1;i<=js[z];i++)if(sj[bs[z][i]]==1)ss--;
}
int main(){
	//freopen("a.in","r",stdin);
	cin>>T;
	for(int u=1;u<=T;u++){
		cin>>n>>m;ss=m;ans=ccd=cd=0;
		for(int i=1;i<=n;i++)k2[i]=kk2[i]=br[i]=bw[i]=0;
		for(int i=1;i<=m;i++){
			scanf("%lld%lld",&a1,&a2);
			DD(a1,a2);
			DDD(a2,a1);
		}
		bl(3);
		cout<<1ll*m*(m-1)/2*(m-2)/3-ans<<'\n';
	}
}