#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10,INF=1e9;
int T,n,m;
namespace Flow{
    const int V=N*2,E=V*2+N*2+N*5;
    int s,t,kk;
    struct edges{
        int to,c,nex;
    }edge[E];
    int cur[V],head[V],d[V];
    void init(int x,int y){
        s=x,t=y,kk=1;
        fill(head+s,head+1+t,0);
    }
    int add(int u,int v,int c){
        edge[++kk]={v,c,head[u]},head[u]=kk;
        edge[++kk]={u,0,head[v]},head[v]=kk;
        return kk-1;
    }
    bool bfs(){
        queue<int>q;
        q.push(s);
        copy(head+s,head+1+t,cur+s);
        fill(d+s,d+1+t,-1),d[s]=0;
        for(int u;!q.empty();){
            u=q.front(),q.pop();
            for(int i=head[u];i;i=edge[i].nex){
                int v=edge[i].to;
                if(edge[i].c&&d[v]==-1)d[v]=d[u]+1,q.push(v);
            }
        }
        return d[t]!=-1;
    }
    int dfs(int u,int lim=INF){
        if(u==t)return lim;
        int flow=0;
        for(int i=cur[u];i&&flow<lim;i=edge[i].nex){
            cur[u]=i;
            int v=edge[i].to;
            if(!edge[i].c||d[v]!=d[u]+1)continue;
            int f=dfs(v,min(lim-flow,edge[i].c));
            if(!f)d[v]=-1;
            edge[i].c-=f,edge[i^1].c+=f,flow+=f;
        }
        return flow;
    }
    int dinic(){
        int flow=0;
        for(;bfs();)flow+=dfs(s);
        return flow;
    }
}
int a[N],b[N],w[N+N];
vector<int>to[N+N];
int pl[N],pr[N],vl[N],vr[N];
void dfs1(int i){
    if(vl[i])return;
    vl[i]=1;
    for(int v:to[i])if(v!=pl[i]+n){
        int j=v-n;
        dfs1(pr[j]);
    }
}
void dfs2(int i){
    if(vr[i])return;
    vr[i]=1;
    for(int v:to[i+n])if(v!=pr[i]){
        int j=v;
        dfs2(pl[j]);
    }
}
void get(){
    scanf("%d%d",&n,&m);
    vector<tuple<int,int,int>>E(m);
    int s=0,t=n+n+1;
    Flow::init(s,t);
    for(auto &[u,v,id]:E){
        scanf("%d%d",&u,&v);
        to[u].push_back(v+n);
        to[v+n].push_back(u);
        id=Flow::add(u,v+n,1);
    }
    for(int i=1;i<=n;i++){
        a[i]=Flow::add(s,i,1);
        b[i]=Flow::add(i+n,t,1);
    }
    int tot=Flow::dinic();
    // cerr<<tot<<endl;
    for(int i=1;i<=n;i++)pl[i]=pr[i]=0,vl[i]=vr[i]=0;
    for(auto [u,v,id]:E){
        if(!Flow::edge[id].c)pl[u]=v,pr[v]=u;
    }
    for(int i=1;i<=n;i++){
        if(Flow::edge[a[i]].c)dfs1(i);
        if(Flow::edge[b[i]].c)dfs2(i);
    }
    // for(int i=1;i<=n+n;i++)cerr<<w[i]<<"\n "[i<n+n];
    int cnt[2][4];
    memset(cnt,0,sizeof cnt);
    // for(int i=1;i<=n+n;i++)cerr<<w[i]<<"\n "[i<n+n];
    for(int i=1;i<=n;i++){
        // cerr<<vl[i]<<"\n "[i<n];
        if(vl[i])cnt[0][1]++;
        if(vr[pl[i]])cnt[0][2]++;
        if(vr[i])cnt[1][2]++;
        if(vl[pr[i]])cnt[1][1]++;
    }
    printf("%lld\n",1ll*cnt[0][1]*cnt[1][2]+1ll*cnt[0][2]*cnt[1][1]);
}
void clr(){
    for(int i=1;i<=n+n;i++)to[i].clear();
}
int main(){
    for(scanf("%d",&T);T--;clr())get();
	return 0;
}