#include<bits/stdc++.h>
using namespace std;
#define N 300010
int head[N],nxt[N<<1],v[N<<1],w[N<<1],now[N],d[N],vis[N];
int n,m,s,t,tot;
inline void add(int x,int y,int z){
	v[++tot]=y;w[tot]=z;
	nxt[tot]=head[x];head[x]=tot;
	v[++tot]=x;w[tot]=0;
	nxt[tot]=head[y];head[y]=tot;
}
inline int bfs(){
	queue<int> q;
	for(int i=0;i<=t;++i){
		d[i]=-1;
	}
	d[s]=0;
	now[s]=head[s];
	q.push(s);
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=nxt[i])if(d[v[i]]==-1&&w[i]){
			q.push(v[i]);
			d[v[i]]=d[x]+1;
			now[v[i]]=head[v[i]];
			if(v[i]==t){
				return 1;
			}
		}
	}
	return 0;
}
int dfs(int x,int flow){
	if(x==t){
		return flow;
	}
	int k,res=0;
	for(int &i=now[x];i&&flow;i=nxt[i]){
		if(w[i]&&d[v[i]]==d[x]+1){
			k=dfs(v[i],min(flow,w[i]));
			if(!k){
				d[v[i]]=-1;
			}
			w[i]-=k;
			w[i^1]+=k;
			flow-=k;
			res+=k;
		}
	}
	return res;
}
void Dfs(int x,int y){
	if(vis[x]){
		return;
	}
	vis[x]=1;
	for(int i=head[x];i;i=nxt[i]){
		if(w[i]==y){
			Dfs(v[i],y);
		}
	}
}
inline void solve(){
	tot=1;
	cin>>n>>m;
	s=n+n+1;
	t=n+n+2;
	for(int i=1;i<=n;++i){
		add(s,i,1);
	}
	for(int i=n+1;i<=n+n;++i){
		add(i,t,1);
	}
	for(int i=1;i<=m;++i){
		int x,y;
		cin>>x>>y;
		add(x,y+n,1);
	}
	while(bfs()){
		dfs(s,0x3f3f3f3f);
	}
//	cout<<ans<<"!!!";
	for(int i=head[s];i;i=nxt[i]){
		if(!w[i]){
			continue;
		}
		Dfs(v[i],1);
	}
	int c1=0;
	for(int i=1;i<=n;++i){
		if(vis[i]){
			++c1;
		}
	}
	memset(vis,0,sizeof(int)*(n+n+3));
	for(int i=head[t];i;i=nxt[i]){
		if(w[i]){
			continue;
		}
		Dfs(v[i],0);
	}
	int c2=0;	
	for(int i=n+1;i<=n+n;++i){
		if(vis[i]){
			++c2;
		}
	}
	memset(vis,0,sizeof(int)*(n+n+3));
	memset(head,0,sizeof(int)*(n+n+3));
	cout<<1ll*c1*c2<<'\n';
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int T;
	cin>>T;
	while(T--){
		solve();
	}
}
/*
1
4 5
1 2
3 2
4 3
1 2
1 2
*/