#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
mt19937 rnd(time(0));
const int MAXN=2e6+5;
const int inf=1e9;
int n,m,s,t;
namespace max_flow{
int dis[MAXN],lst[MAXN],cur[MAXN],tot=1,node;
bool vis1[MAXN],vis2[MAXN];
struct edge{int to,val,nxt;}e[MAXN];
void init_node(int x){
	for(int i=1;i<=x;i++) dis[i]=lst[i]=cur[i]=vis1[i]=vis2[i]=0;
	tot=1;
	node=x;
} 
void add(int u,int v,int w){
	++tot;
	e[tot].to=v,e[tot].val=w,e[tot].nxt=lst[u];lst[u]=tot;
	return;
}
void Add(int u,int v,int w){
	add(u,v,w);add(v,u,0);
}
bool BFS(){
	for(int i=1;i<=node;i++) dis[i]=0;
	dis[s]=1;
	queue<int> q;q.push(s);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=lst[u];i;i=e[i].nxt){
			int v=e[i].to,w=e[i].val;
			if(w&&!dis[v]){
				dis[v]=dis[u]+1;
				q.push(v);
			}
		}
	}
	return dis[t];
}
ll dinic(int u,int flow=inf){
	if(u==t) return flow;
	int fl=flow;
	for(int i=cur[u];i&&flow;i=e[i].nxt){
		int v=e[i].to,w=e[i].val;cur[u]=i;
		if(w&&dis[v]==dis[u]+1){
			int val=dinic(v,min(flow,w));
			flow-=val;
			e[i].val-=val;e[i^1].val+=val;
		}
	}
	return fl-flow;
}
ll max_flow(){
	ll ans=0;
	while(BFS()){
		for(int i=1;i<=node;i++) cur[i]=lst[i];
		ans+=dinic(s);
	}
	return ans;
}
void dfs1(int u){
	if(vis1[u]) return;
	vis1[u]=true;
	for(int i=lst[u];i;i=e[i].nxt) if(e[i].val){
		dfs1(e[i].to);
	}
}
void dfs2(int u){
	if(vis2[u]) return;
	vis2[u]=true;
	for(int i=lst[u];i;i=e[i].nxt) if(!e[i].val){
		dfs2(e[i].to);
	}
}
}
void solve(){
	cin>>n>>m;s=2*n+1,t=2*n+2;
	max_flow::init_node(2*n+2);
	for(int i=1;i<=n;i++) max_flow::Add(s,i,1),max_flow::Add(i+n,t,1);
	for(int i=1;i<=m;i++){
		int u,v;cin>>u>>v;
		max_flow::Add(u,v+n,1);
	}
	max_flow::max_flow();
	max_flow::dfs1(s);
	max_flow::dfs2(t);
	ll ls=0,rs=0;
	for(int i=1;i<=n;i++){
		ls+=max_flow::vis1[i];
		rs+=max_flow::vis2[i+n];
	}
	cout<<ls*rs<<'\n';
}
int main(){
	ios::sync_with_stdio(false);
	// freopen("Otomachi_Una.in","r",stdin);
	// freopen("Otomachi_Una.out","w",stdout);
	int _;cin>>_;
	while(_--) solve();
	return 0;
}