#include<bits/stdc++.h>
using namespace std;
#define M 200005
#define ll long long
int hd[M<<1],nx[M<<2],to[M<<2],val[M<<2],cnt=1,n,m,vis[M<<2];
void add(int x,int y,int w){
	nx[++cnt]=hd[x];hd[x]=cnt;to[cnt]=y;val[cnt]=w;
	nx[++cnt]=hd[y];hd[y]=cnt;to[cnt]=x;val[cnt]=0;
}
int C[M<<1],dis[M<<1],sk[M<<1];
bool bfs(){
	for(int i=1;i<=2*n+2;++i)C[i]=hd[i],dis[i]=0;
	int l=1,r=0;
	dis[2*n+1]=1;sk[++r]=2*n+1;
	while(l<=r){
		int p=sk[l++];
		for(int i=hd[p];i;i=nx[i])if(val[i]){
			int v=to[i];
			if(!dis[v]){
				dis[v]=dis[p]+1,sk[++r]=v;
				if(v==2*n+2)return 1;
			}
		}
	}
	return 0;
}
int dfs(int x,int w){
	if(x==2*n+2||!w)return w;
	int ans=0;
	for(int &i=C[x];i;i=nx[i])if(val[i]){
		int v=to[i];
		if(dis[v]!=dis[x]+1)continue;
		int s=dfs(v,min(val[i],w));
		ans+=s;w-=s;
		val[i]-=s;val[i^1]+=s;
		if(!w)break;
	}
	return ans;
}
int dic(){
	int ans=0;
	while(bfs())ans+=dfs(2*n+1,1e9);
	return ans;
}
void init(){
	cnt=1;
	for(int i=1;i<=2*n+2;++i)hd[i]=vis[i]=0;
}
void Dfs(int x,int f){
	if(vis[x])return;
	vis[x]=f+1;
	for(int i=hd[x];i;i=nx[i])if(val[i]==f)Dfs(to[i],f);
}
void solve(){
	scanf("%d%d",&n,&m);
	for(int i=1,u,v;i<=m;++i){
		scanf("%d%d",&u,&v);
		add(u,v+n,1);
	}
	for(int i=1;i<=n;++i)add(2*n+1,i,1),add(i+n,2*n+2,1);
	dic();
	int w1=0,w2=0,w3=0,w4=0;
	Dfs(2*n+1,1);
	Dfs(2*n+2,0);
	for(int i=1;i<=n;++i)w1+=vis[i]==1,w2+=vis[i]==2,w3+=vis[i+n]==1,w4+=vis[i+n]==2;
	printf("%lld\n",1ll*w1*w4);
	init();
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--)solve();
}