#include <bits/stdc++.h>
#define int long long
using namespace std;
int Read(){
	int x=0;
	char ch=getchar();bool f=0;
	while(ch<'0'||ch>'9') if(ch=='-')f=1,ch=getchar(); else if(ch==EOF)return 0; else ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
int h[800005],nxt[800005],to[800005],val[800005];
int cnt=1;
int n,m,s,t;
int ls[800005],lt[800005];
void link(int x,int y,int z){
	nxt[++cnt]=h[x];
	h[x]=cnt;
	to[cnt]=y;
	val[cnt]=z;
	if(x==2*n+1) ls[y]=cnt;
	if(y==2*n+2) lt[x]=cnt;
	nxt[++cnt]=h[y];
	h[y]=cnt;
	to[cnt]=x;
	val[cnt]=0;
	return;
}
const int inf=0x3f3f3f3f3f3f3f3f;
int dis[800005],now[800005];
queue<int> q;
bool bfs(){
	bool flag=0;
	for(int i=1;i<=2*n+2;i++) dis[i]=inf;
	q.push(s);
	dis[s]=0;
	now[s]=h[s];
	while(!q.empty()){
		int x=q.front();
//		cout<<x<<endl;
		q.pop();
		for(int i=h[x];i;i=nxt[i]){
			if(dis[to[i]]==inf&&val[i]>0){
				dis[to[i]]=dis[x]+1;
				now[to[i]]=h[to[i]];
				q.push(to[i]);
				if(to[i]==t) flag=1;
			}
		}
	}
	return flag;
}
int dfs(int x,int fl){
	if(x==t) return fl;
	int ans=0;
	for(int i=now[x];i&&fl;i=nxt[i]){
		now[x]=i;
		if(val[i]>0&&dis[to[i]]==dis[x]+1){
			int k=dfs(to[i],min(fl,val[i]));
			if(k==0) dis[to[i]]=inf;
			val[i]-=k;
			val[i^1]+=k;
			fl-=k;
			ans+=k;
		}
	}
	return ans;
}
bool vis1[800005];
void dfs(int x){
	vis1[x]=1;
	for(int i=h[x];i;i=nxt[i]){
		int p=to[i];
		if((!val[i])||vis1[p])continue;
		dfs(p);
	}return;
}
void dfs1(int x){
	vis1[x]=1;
	for(int i=h[x];i;i=nxt[i]){
		int p=to[i];
		if(val[i]||vis1[p])continue;
		dfs(p);
	}return;
}
bool ans[800005];
signed main() {
	int T=Read();
	while(T--){
		n=Read(),m=Read();
		for(int i=1;i<=2*n+2;i++)h[i]=0,ans[i]=0;
		while(m--){
			int x=Read(),y=Read();
			link(x,y+n,1);
		}
		for(int i=1;i<=n;i++){
			link(2*n+1,i,1);
		}for(int i=n+1;i<=2*n;i++){
			link(i,2*n+2,1);
		}
		s=2*n+1,t=2*n+2;
		int ans=0;
		while(bfs())ans+=dfs(s,inf);
//		cout<<ans<<endl;
		int ans1=0,ans2=0;
		for(int i=1;i<=2*n+2;i++)vis1[i]=0;
		dfs(2*n+1);
		for(int i=1;i<=n;i++) ans1+=vis1[i],vis1[i]=0;
		for(int i=n+1;i<=2*n+2;i++) vis1[i]=0;
		dfs1(2*n+2);
		for(int i=n+1;i<=2*n;i++) ans2+=vis1[i];
		printf("%lld\n",ans1*ans2);
	}
	
	return 0;
}