#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll T,n,m,S;
ll G1[55],G2[55],vis,num1[55][55],num2[55][55],ans,n1,n2;
queue<ll> q,q1,q2,q3,Q1,Q2,q4,q5;
struct node{
	ll u,v,op;//0:spare 1:deleted 2:unsed 
}E[2505];
void bfs(ll GG[],ll num[][55],queue<ll> &Q){
	q.push(1ll);
	vis=1ll;
	while(!q.empty()){
		ll u=q.front();
		q.pop();
		ll G=GG[u];
		G^=(G&vis);
		vis|=G;
		for(;G;G^=G&-G){
			ll v=__builtin_ctzll(G)+1ll;
			q.push(v);
			Q.push(num[u][v]);
		}
	}
}
bool check(){
	while(!Q1.empty())Q1.pop();
	bfs(G1,num1,Q1);
	while(!Q2.empty())Q2.pop();
	bfs(G2,num2,Q2);
	return (ll)Q1.size()==n-1&&(ll)Q2.size()==n-1;
}
int main(){
	scanf("%lld",&T);
	while(T--){
		ans=0;
		scanf("%lld%lld",&n,&m);
		for(int i=0;i<=n;i++)
			for(int j=0;j<=n;j++)
				num1[i][j]=num2[i][j]=0;
		for(int i=0;i<=n;i++)G1[i]=G2[i]=0;
		S=(1ll<<n)-1;
		for(ll i=1;i<=m;i++){
			ll u,v;
			scanf("%lld%lld",&u,&v);
			E[i].u=u,E[i].v=v;
			G1[u]|=(1ll<<(v-1));
			G2[v]|=(1ll<<(u-1));
			num1[u][v]=i,num2[v][u]=i;
		}
		bfs(G1,num1,q1);bfs(G2,num2,q1);
		while(!q1.empty()){
			ll i=q1.front(),u=E[i].u,v=E[i].v;
			q1.pop();
			if(E[i].op!=0)continue;
			E[i].op=1;n1++;
			G1[u]^=(1ll<<(v-1));
			G2[v]^=(1ll<<(u-1));
			if(check()){
				bfs(G1,num1,q2);bfs(G2,num2,q2);
				while(!q2.empty()){
					ll j=q2.front(),u=E[j].u,v=E[j].v;
					q4.push(j);q2.pop();
					if(E[j].op!=0)continue;
					E[j].op=2;n2++;
					G1[u]^=(1ll<<(v-1));
					G2[v]^=(1ll<<(u-1));
					if(check()){
						bfs(G1,num1,q3);bfs(G2,num2,q3);
						while(!q3.empty()){
							ll k=q3.front(),u=E[k].u,v=E[k].v;
							q5.push(k);q3.pop();
							if(E[k].op!=0)continue;
							G1[u]^=(1ll<<(v-1));
							G2[v]^=(1ll<<(u-1));
							E[k].op=3;
							if(!check())ans++;
							G1[u]^=(1ll<<(v-1));
							G2[v]^=(1ll<<(u-1));
						}
						while(!q5.empty()){
							ll k=q5.front();
							q5.pop();
							if(E[k].op==3)E[k].op=0;
						}
					}
					
					else ans+=(m-n1-n2);
					
					G1[u]^=(1ll<<(v-1));
					G2[v]^=(1ll<<(u-1));
					
				}
				while(!q4.empty()){
					ll j=q4.front();
					q4.pop();
					if(E[j].op==2)E[j].op=0;
				}
				n2=0;
			}
			
			else ans+=(ll)(m-n1)*(m-n1-1)/2;
			
			G1[u]^=(1ll<<(v-1));
			G2[v]^=(1ll<<(u-1));
		}
		n1=0;
		printf("%lld\n",ans);
	}
}