#include <bits/extc++.h>
#include <bits/stdc++.h>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
const int maxn=2e5+5;
class A
{
public:
    int to;
    long long cap,flow;
    int r; //反向边的位置
};
vector<A> G[maxn];
int pre[maxn],preedge[maxn],d[maxn],num[maxn],cur[maxn]; //d为与t的距离，num[i]为距离为i的点的数量,cur为当前弧
bitset<maxn> vis;
void addedge(int u,int v,int cap) //网络流的特殊建图
{
    G[u].push_back({v,cap,0,(int)G[v].size()});
    G[v].push_back({u,0,0,(int)G[u].size()-1});
}
long long add(int s,int t) //将当前轮次的贡献统计
{
    int now=t;
    long long a=99999999999999;
    while(now!=s)
    {
        auto &p=G[pre[now]][preedge[now]];
        a=min(a,p.cap-p.flow);
        now=pre[now];
    }
    now=t;
    while(now!=s)
    {
        auto &p=G[pre[now]][preedge[now]];
        p.flow+=a;
        G[p.to][p.r].flow-=a;
        now=pre[now];
    }
    return a;
}
long long ISAP(int s,int t,int n) //s为源点，t为汇点，n为边数，求最大流
{
    queue<int> q; //BFS对图分层
    q.push(t);
    vis[t]=1;
    while (!q.empty())
    {
        int now=q.front();
        q.pop();
        for(auto i:G[now])
        {
            if(!vis[i.to]&&G[i.to][i.r].cap) //找反向边有容量的
            {
                vis[i.to]=1;
                d[i.to]=d[now]+1;
                q.push(i.to);
            }
        }
    }
    for(int i=0;i<=n;i++)
        num[d[i]]++;
    int now=s;
    long long flow=0;
    while(d[s]<=n)
    {
        if(now==t)
        {
            flow+=add(s,t);
            now=s;
        }
        bool ok=false;
        for(int i=cur[now];i<G[now].size();i++)
        {
            auto &v=G[now][i];
            if(v.cap>v.flow&&d[now]==d[v.to]+1)
            {
                ok=true;
                pre[v.to]=now;
                preedge[v.to]=i;
                cur[now]=i;
                now=v.to;
                break;
            }
        }
        if(!ok) //没有成功传流
        {
            int m=4;
            for(int i=0;i<G[now].size();i++)
            {
                auto &v=G[now][i];
                if(v.cap>v.flow)
                    m=min(m,d[v.to]);
            }
            num[d[now]]--;
            if(!num[d[now]])
                break;
            d[now]=m+1; //下降高度
            num[d[now]]++;
            cur[now]=0;
            if(now!=s) //回溯
                now=pre[now];
        }
    }
    return flow;
}
inline long long input(){
    long long n=0;
    int f=1;
    char c=getchar();
    while(c<'0' || c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0' && c<='9'){
        n=(n<<3)+(n<<1)+(c^48);
        c=getchar();
    }
    return n*f;
}
int n;
long long ans=0,ans2=0;
bitset<maxn> flag;
int flag2[maxn];
void dfs1(int d)
{
	if(flag[d])
		return;
	flag[d]=1;
	if(d>=1&&d<=n)
		ans++;
	for(auto i:G[d])
		if(!flag[i.to]&&i.cap-i.flow)
			dfs1(i.to);
}
void dfs2(int d)
{
	if(flag2[d])
		return;
	flag2[d]=1;
	if(d>=1+n&&d<=2*n)
		ans2++;
	for(auto i:G[d])
		if(!flag2[i.to]&&i.cap-i.flow==0)
			dfs2(i.to);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t,m,u,v;
    t=input();
    while (t--)
    {
		n=input();
		m=input();
		for(int i=0;i<=2*n+1;i++)
		{
			G[i].clear();
			pre[i]=preedge[i]=d[i]=num[i]=cur[i]=0; //d为与t的距离，num[i]为距离为i的点的数量,cur为当前弧
			vis[i]=flag[i]=flag2[i]=0;
		}
		for(int i=1;i<=n;i++)
		{
			addedge(0,i,1);
			addedge(i+n,2*n+1,1);
		}
		for(int i=1;i<=m;i++)
		{
			u=input();
			v=input();
			addedge(u,v+n,1);
		}
		ISAP(0,2*n+1,2*n+1);
		ans=0,ans2=0;
		dfs1(0);
		dfs2(2*n+1);
		printf("%lld\n",ans*ans2);
    }
}