#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m,head[400005],s,t,tot,dis[400005],cur[400005];
struct ss{
    int node,nxt,w;
}e[2400005];
set<pair<int,int> > st;
void add(int u,int v,int w)
{
    e[++tot]=(ss){v,head[u],w};
    head[u]=tot;
    e[++tot]=(ss){u,head[v],0};
    head[v]=tot;
}
bool bfs(int u,int v)
{
    for(int i=s;i<=t;i++)
        dis[i]=inf;
    queue<int> q;
    q.push(u);dis[u]=0;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=e[i].nxt)
        {
            if(!e[i].w)continue;
            int y=e[i].node;
            if(dis[y]>dis[x]+1)
            {
                dis[y]=dis[x]+1;
                q.push(y);
            }
        }
    }
    return dis[v]!=inf;
}
int dinic(int x,int now)
{
    if(!now||x==t)return now;
    int ans=0;
    for(int i=cur[x];i;i=e[i].nxt)
    {
        cur[x]=i;
        if(!e[i].w)continue;
        int y=e[i].node;
        if(dis[y]==dis[x]+1)
        {
            int v=dinic(y,min(e[i].w,now-ans));
            ans+=v;
            e[i].w-=v;
            e[i^1].w+=v;
            if(ans==now)break;
        }
    }
    return ans;
}
void solve(void)
{
    tot=1;
    st.clear();
    cin>>n>>m;
    s=0;t=n+n+1;
    for(int i=s;i<=t;i++)
        head[i]=0;
    for(int i=1;i<=n;i++)
    {
        add(s,i,1);
        add(i+n,t,1);
    }
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        if(st.count(make_pair(u,v)))
            continue;
        add(u,v+n,1);
        st.insert(make_pair(u,v));
    }
    int sum=0,L=0,R=0;
    while(bfs(s,t))
    {
        for(int i=s;i<=t;i++)
            cur[i]=head[i];
        sum+=dinic(s,inf);
    }
    //cerr<<sum<<endl;
    for(int i=1;i<=n;i++)
        if(dis[i]!=inf)L++;
    for(int i=2;i<=tot;i+=2)
    {
        swap(e[i].w,e[i^1].w);
    }
    bfs(t,s);
    for(int i=1;i<=n;i++)
        if(dis[i+n]!=inf)R++;
    cout<<1ll*L*R<<'\n';
}
signed main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}