#include <bits/stdc++.h>
using namespace std;
#define fo(i,a,b) for(int i=(a);i<=(b);i++)
#define inf 1000000000
#define LL int
const int N=200010,M=1000010;
int n,m,s,t;
int cur[N];
LL dis[N],gap[N],maxflow=0;
int vis[N],sz[N];
struct edge
{
  int x;
  int y;
  LL val;
};
vector<int> e[N*2];
vector<edge> a;
void add(int u,int v,int w)
{
  a.push_back({u,v,w});
  e[u].push_back(a.size()-1);
}
void bfs()
{
  fo(i,1,max(n,t))dis[i]=inf;
  dis[t]=0;
  gap[0]=1;
  queue<int> q;
  q.push(t);
  while(!q.empty())
  {
    int u=q.front();
    q.pop();
    for(int num:e[u])
    {
      int v=a[num].x^a[num].y^u;
      if(dis[v]==inf) dis[v]=dis[u]+1,gap[dis[v]]++,q.push(v);
    }
  }
}
LL dfs(int u,LL flow)
{
  LL used=0;
  if(u==t)
  {
    maxflow+=flow;
    return flow;
  }
  if(dis[s]>t) return 0;
  for(int i=cur[u]; i<(int)sz[u]; i++)
  {
    cur[u]=i;
    int num=e[u][i];
    int v=a[num].x^a[num].y^u;
    if(a[num].val&&dis[v]+1==dis[u])
    {
      LL cnt=dfs(v,min(a[num].val,flow-used));
      a[num].val-=cnt;
      a[num^1].val+=cnt;
      used+=cnt;
    }
    if(flow-used==0) return used;
  }
  if(!(--gap[dis[u]])) dis[s]=t+1;
  gap[++dis[u]]++;
  return used;
}
LL ans_bfs(int start,int type)
{
    LL ans=0;
    queue<int> q;
    q.push(start);
    fo(i,1,t) vis[i]=0;
    vis[start]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int num:e[u])
        {
            int v=a[num].x^a[num].y^u;
            if(type==1&&a[num].val==1)
            {
                if(!vis[v])
                {
                    vis[v]=1;
                    if(v<=n)
                    {
                        ans++;
                    }
                    q.push(v);
                }
            }
            else if(type==2&&a[num].val==0)
            {
                if(!vis[v])
                {
                    vis[v]=1;
                    if(v>n&&v!=s)
                    {
                        ans++;
                    }
                    q.push(v);
                }
            }
        }
    }
    return ans;
}
void solve()
{
  
  vector<pair<int, int> > q;
  scanf("%d%d",&n,&m);
  s=2*n+1;
  t=2*n+2;
  a.clear();
  maxflow=0;
  fo(i,1,t) 
  {
    e[i].clear();
    gap[i]=0;
    sz[i]=0;
  }
  
  fo(i,1,m)
  {
    int u,v;
    scanf("%d%d",&u,&v);
    v+=n;
    add(u,v,1);
    add(v,u,0);
  }
  
  
  fo(i,1,n)
  {
    add(s,i,1);
    add(i,s,0);
    add(i+n,t,1);
    add(t,i+n,0);
  }
  fo(i,1,t) sz[i]=e[i].size();
  bfs();
  while(dis[s]<t)
  {
     fill(cur + 1, cur + t + 1, 0);
    dfs(s,inf);
  }
  if(maxflow==n) cout<<0<<endl; 
  else cout<<(long long)ans_bfs(s,1)*(long long)ans_bfs(t,2)<<endl;
  return ;
}
int main()
{
    int tcase;
    scanf("%d",&tcase);
    while(tcase--) solve();
}