#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
const int MX=100010;
const int inf=0x3fffffff;

int Cases, N, M, S, T, siz;
int head[2*MX], cnt=1;
int dep[2*MX], cur[2*MX];
bool vis[2*MX];
int read()
{
    int r=0, f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {r=r*10+ch-'0'; ch=getchar();}
    return r*f;
}
struct edge{int nxt, to, c;}e[20*MX];
inline void ae(int u, int v, int c)
{
    e[++cnt].to=v; e[cnt].nxt=head[u]; head[u]=cnt; e[cnt].c=c;
    e[++cnt].to=u; e[cnt].nxt=head[v]; head[v]=cnt; e[cnt].c=0;
}
queue<int> q, q1, q2;
bool bfs()
{
    for(int i=1;i<=siz;i++) dep[i]=0;
    while(!q.empty()) q.pop();
    q.push(S); dep[S]=1; cur[S]=head[S];
    while(!q.empty())
    {
        int x=q.front(); q.pop();
        for(int i=head[x];i;i=e[i].nxt)
        {
            int y=e[i].to;
            if(dep[y]||!e[i].c) continue;
            dep[y]=dep[x]+1;
            cur[y]=head[y];
            if(y==T) return 1;
            q.push(y);
        }
    }
    return 0;
}
int find(int u, int lim)
{
    if(u==T) return lim;
    int res=0;
    for(int i=cur[u];i&&res<lim;i=e[i].nxt)
    {
        cur[u]=i;
        int y=e[i].to;
        if(dep[y]!=dep[u]+1||!e[i].c) continue;
        int t=find(y,min(e[i].c,lim-res));
        if(!t) dep[y]=0;
        e[i].c-=t; e[i^1].c+=t; res+=t;
    }
    return res;
}
int dinic()
{
    int ans=0, flow;
    while(bfs())
        while(flow=find(S,inf))
            ans+=flow;
    return ans;
}
int main()
{
    // freopen("testdata.in","r",stdin);
    Cases=read();
    while(Cases--)
    {
        N=read(); M=read(); 
        S=2*N+1; T=S+1; siz=2*N+2;
        for(int i=1;i<=siz;i++) head[i]=0;
        cnt=1;
        for(int i=1;i<=M;i++)
        {
            int u=read(), v=read();
            ae(u,v+N,1);
        }
        for(int i=1;i<=N;i++)
            ae(S,i,1), ae(i+N,T,1);
        int match=dinic();  
        // cout << "match=" << match << '\n';
        int s1=0, s2=0;
        while(!q1.empty()) q1.pop();
        while(!q2.empty()) q2.pop();
        for(int i=1;i<=siz;i++) vis[i]=0;
        q1.push(S);
        while(!q1.empty())
        {
            int x=q1.front(); q1.pop();
            if(vis[x]) continue; vis[x]=1;
            // cout << "x=" << x << '\n';
            for(int i=head[x];i;i=e[i].nxt)
            {
                int y=e[i].to;
                if(!e[i].c||y==S||y==T) continue;
                s1+=(y<=N); q1.push(y);
            }
        }
        // cout << "s1=" << s1 << '\n';
        for(int i=1;i<=siz;i++) vis[i]=0;
        q2.push(T);
        while(!q2.empty())
        {
            int x=q2.front(); q2.pop();
            if(vis[x]) continue; vis[x]=1;
            // cout << "x=" << x << '\n';
            for(int i=head[x];i;i=e[i].nxt)
            {
                int y=e[i].to;
                if(!e[i].c||y==T||y==S) continue;
                s2+=(y>N); q2.push(y);
            }
        }
        ll ans=1ll*s1*s2;
        cout << ans << '\n';
        for(int i=1;i<=siz;i++) head[i]=0;
        cnt=1;
    }
    return (0-0);
}