#include<bits/stdc++.h>
using namespace std;
const int N=1e5+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,q.push(s);
        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],vis[N+N];
vector<int>to[N+N];
void dfs(int u){
    vis[u]=1;
    for(int v:to[u])if(!vis[v]){
        w[v]|=w[u],dfs(v);
    }
}
void get(){
    scanf("%d%d",&n,&m);
    vector<pair<int,int>>E(m);
    int s=0,t=n+n+1;
    Flow::init(s,t);
    for(auto &[u,v]:E){
        scanf("%d%d",&u,&v);
        to[u].push_back(v+n);
        to[v+n].push_back(u);
        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++){
        if(Flow::edge[a[i]].c)w[i]=1;
        else w[i]=0;
        if(Flow::edge[b[i]].c)w[i+n]=2;
        else w[i+n]=0;
    }
    // for(int i=1;i<=n+n;i++)cerr<<w[i]<<"\n "[i<n+n];
    fill(vis,vis+1+n+n,0);
    for(int i=1;i<=n+n;i++)if(!vis[i]&&w[i])dfs(i);
    int cnt[2][3];
    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++){
        cnt[0][w[i]]++,cnt[1][w[i+n]]++;
    }
    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;
}