#include<bits/stdc++.h>
using namespace std;
#define LL long long
struct edges{
	LL to,flow,nt;
}a[2000005],b[2000005];
LL n,i,j,k,m,ans=0,cnt=1,s,t,x,y,z,sum1,sum2,num1,num2,cnt1=0,t1;
LL nxt[200005],depth[200005],gap[200005],nxt1[200005];
bool flag[200005],vis[200005];
const LL inf=0x7fffffff;
void add(LL x,LL y,LL z){
	a[++cnt].to=y;a[cnt].flow=z;a[cnt].nt=nxt[x];nxt[x]=cnt;
	a[++cnt].to=x;a[cnt].flow=0;a[cnt].nt=nxt[y];nxt[y]=cnt;
}
void add1(LL x,LL y){
	b[++cnt1].to=y;b[cnt1].nt=nxt1[x];nxt1[x]=cnt1;
}
void bfs(){
	for(LL i=1;i<=t;i++)
	  depth[i]=inf;
	queue<LL> q;
	q.push(t);
	depth[t]=0;
	while(!q.empty()){
		LL tmp=q.front();q.pop();
		for(LL i=nxt[tmp];i;i=a[i].nt){
			if(depth[a[i].to]==inf){
				depth[a[i].to]=depth[tmp]+1;
				gap[depth[a[i].to]]++;
				q.push(a[i].to);
			}
		}
	}
}
LL dfs(LL x,LL flow){
	if(x==t){
		ans+=flow;
		//printf("%lld\n",flow);
		return flow;
	}
	LL sum=0;
	for(LL i=nxt[x];i;i=a[i].nt){
		if(depth[a[i].to]+1==depth[x] && a[i].flow!=0){
			LL tmp=dfs(a[i].to,min(a[i].flow,flow-sum));
			if(tmp>0){
				a[i].flow-=tmp;
				a[i^1].flow+=tmp;
				sum+=tmp;
			}
			if(sum==flow) return flow;
		}
	}
	gap[depth[x]]--;
	if(gap[depth[x]]==0) depth[s]=t;
	gap[++depth[x]]++;
	return sum;
}
void isap(){
	while(depth[s]<=t) dfs(s,0x7fffffffffffffff);
}
void dfs1(LL father,LL x){
	vis[x]=true;
	if(x<=n){
		sum1++;
		if(flag[x]==true) num1++;
	}
	else{
		sum2++;
		if(flag[x]==true) num2++; 
	}
	for(LL i=nxt1[x];i;i=b[i].nt)
	  if(vis[b[i].to]==false) dfs1(x,b[i].to);
}
int main(){
	scanf("%lld",&t1);
	while(t1--){
		for(i=0;i<=cnt;i++)
		  a[i].to=a[i].nt=a[i].flow=0;
		for(i=0;i<=cnt1;i++)
		  b[i].to=b[i].nt=0;
		cnt=1,cnt1=0;
		for(i=0;i<=2*n+2;i++)
		  nxt[i]=0,vis[i]=false,flag[i]=false,gap[i]=0,nxt1[i]=0;
		scanf("%lld%lld",&n,&m);
		s=2*n+1,t=2*n+2;
		for(i=1;i<=n;i++)
		  add(s,i,1),add(i+n,t,1);
		for(i=1;i<=m;i++){
			scanf("%lld%lld",&x,&y);
			add(x,n+y,1);add1(x,n+y),add1(n+y,x);
		}
		bfs();
		isap();
		for(i=1;i<=n;i++){
			if(a[4*(i-1)+2].flow==0) flag[i]=true;
			if(a[4*(i-1)+4].flow==0) flag[i+n]=true;
			//printf("%lld %lld\n",a[4*(i-1)+2].flow,a[4*(i-1)+4].flow);
		}
		//for(i=1;i<=2*n;i++)
		//  printf("%lld ",flag[i]);
		//printf("\n");
		LL ans1=0,ans2=0,ans=0;
		for(i=1;i<=2*n;i++)
		  if(vis[i]==false){
		  	sum1=sum2=num1=num2=0;
		  	dfs1(0,i);
		  	if(sum1>num1) ans1+=sum1;
		  	if(sum2>num2) ans2+=sum2;
		  	if(sum1>num1 && sum2>num2) ans+=sum1*sum2;
		  	//printf("%lld %lld %lld %lld %lld\n",i,sum1,sum2,num1,num2);
		  }
		printf("%lld\n",ans1*ans2-ans);
	}
	return 0;
}