#include<bits/stdc++.h>
using namespace std;
int cur[200005],dis[200005];
int n,m,num,head = 1,tot;
vector<int>p[200005];
int s,t;
struct edge{
	int fl,to;
}e[1000005];
void add(int a,int b){
	e[++head].to = b,e[head].fl = 1;
	p[a].push_back(head);
	e[++head].to = a,e[head].fl = 0;
	p[b].push_back(head);return; 
}bool bfs(){
	queue<int>q;
	for(int i = 1;i<=tot;i++)dis[i] = tot+2;
	dis[s] = 0;q.push(s);
	while(!q.empty()){
		int now =q.front();q.pop();
		for(int i =0;i<p[now].size();i++){
			int to  =e[p[now][i]].to,fl = e[p[now][i]].fl;
			//cout << now << " " << to  << " " << fl<< '\n';
			if(!fl)continue;
			if(dis[to]>dis[now]+1){
				q.push(to);
				dis[to] = dis[now]+1;
			}
		}
	}//cout << dis[t] << '\n';
	return (dis[t]!=tot+2); 
}int dfs(int now,int f){
	//cout << now << " " << f << '\n';
	if(now == t or !f)return f;
	int res =0;
	for(int i =cur[now];i<p[now].size();i++){
		//cout << i << '\n';
		int to = e[p[now][i]].to,fl = e[p[now][i]].fl,nw;
		cur[now] = i;
		if(!fl or (dis[now]+1!=dis[to]))continue;
		if(nw = dfs(to,min(fl,f))){
			res+=nw,f-=nw;
			e[p[now][i]].fl-=nw,e[p[now][i]^1].fl+=nw;
			if(!f)break;
		}
	}return res;
}
int Dinic(){int ans = 0;
	while(bfs()){
		for(int i =0;i<=tot;i++)cur[i] = 0;
		ans+=dfs(s,200005);
	}return ans;
}
bool vis1[500005],vis2[500005];
void dfs1(int now){
	vis1[now] = 1;
	for(auto x:p[now]){
		int to = e[x].to,fl = e[x].fl;
		if(fl and !vis1[to])dfs1(to);
	}
}
void dfs2(int now){
	vis2[now] = 1;
	for(auto x:p[now]){
		int to = e[x].to,fl = e[x].fl;
		if(!fl and !vis2[to])dfs2(to);
	} 
}
void solve(){
	for(int i =0;i<=tot;i++)p[i].clear();
	for(int i =0;i<=tot;i++)vis1[i]=0,vis2[i]=0;
	cin >> n >> m;
	tot = n+n+2;
	for(int i =1;i<=m;i++){
		int a,b;cin >> a >> b;b+=n;
		add(a,b);
	}for(int i = 1;i<=n;i++)add(tot-1,i);
	for(int i = 1;i<=n;i++)add(i+n,tot);
	s=  tot-1,t = tot;
	Dinic();
	dfs1(s),dfs2(t);
	int cnt1 =0,cnt2 = 0;
	for(int i = 1;i<=n;i++)if(vis1[i])cnt1++;
	for(int i = n+1;i<=n+n;i++)if(vis2[i])cnt2++;
	cout << 1ll*cnt1*cnt2 << endl;
}
signed main(){
	int t;cin >> t;
	while(t--)solve();
	return 0;
}/*
 3
 4 3
 1 2
 3 2
 4 3
 3 3
 1 3
 2 2
 3 1
 3 2
 1 2
 1 2
*/