#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[200005],nxt[1600005],to[1600005],val[1600005];
int cnt=1;
int n,m,s,t;
int ls[100005],lt[200005];
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[200005],now[200005];
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[200005];
void dfs2(int x){
vis1[x]=1;
for(int i=h[x];i;i=nxt[i]){
int p=to[i];
if((!val[i])||vis1[p])continue;
dfs2(p);
}return;
}
void dfs1(int x){
vis1[x]=1;
for(int i=h[x];i;i=nxt[i]){
int p=to[i];
// cout<<x<<' '<<p<<' '<<vis1[p]<<endl;
if(val[i]||vis1[p])continue;
dfs1(p);
}return;
}
signed main() {
int T=Read();
while(T--){
n=Read(),m=Read();
for(int i=1;i<=2*n+3;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;
while(bfs())dfs(s,inf);
// cout<<ans<<endl;
int ans1=0,ans2=0;
for(int i=1;i<=2*n+3;i++)vis1[i]=0;
dfs2(2*n+1);
for(int i=1;i<=n;i++)ans1+=vis1[i],vis1[i]=0;
for(int i=n+1;i<=2*n+3;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;
}