#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld double
#define uint unsigned long long
#define endl '\n'
// #define ll __int128
namespace OOO
{
	void fast_io()
	{
		std::ios::sync_with_stdio(false);
		std::cin.tie(0);
		std::cout.tie(0);
	}
	int get_int()
	{
	    int x=0;
	    bool y=0;
	    char c=getchar();
	    for(;c<'0'||c>'9';c=getchar())
	    {
	        if(c=='-')
	        {
	            y=1;
	        }
	    }
	    for(;c>='0'&&c<='9';c=getchar())
	    {
	        x=(x<<3)+(x<<1)+c-'0';
	    }
	    return y?-x:x;
	}
	void out_int(int x)
	{
		if(x==0)
		{
			putchar('0');
			return;
		}
		int s=1;
		for(;s<=x;s=(s<<3)+(s<<1))
		{
		}
		for(s/=10;s;s/=10)
		{
			putchar(x/s-x/(s*10)*10+'0');
		}
	}
	int fast_pow(int a,int b,int mod)
    {
        int ans=1;
        if(a>mod)
        {
        	a%=mod;
		}
        for(;b;b>>=1)
        {
            if(b&1)
            {
                ans=ans*a;
				if(ans>mod)
            	{
            		ans%=mod;
				}
            }
            a=a*a;
            if(a>mod)
            {
            	a%=mod;
			}
        }
        return ans;
    }
}using namespace OOO;
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")
class Edge
{
	public:
		int st,to;
		int num;
		int nxt;
		Edge(int _st=0,int _to=0,int _num=0,int _nxt=0)
		:st(_st),to(_to),num(_num),nxt(_nxt)
		{
		}
};
class Road
{
	public:
		vector<Edge> edge;
		vector<int> tope;
		int cnt;
		
		void init(int p_num=0,int edge_num=0)
		{
			edge=vector<Edge>(edge_num+1);
			tope=vector<int>(p_num+1,0);
			cnt=0;
		}
		int newnode()
		{
			if(cnt==edge.size()-1)
			{
				edge.push_back(Edge());
			}
			return ++cnt;
		}
		void addedge(int a,int b,int num=0)
		{
			int s=max(a,b);
			if(s>=tope.size())
			{
				tope.resize(s+1);
			}
			edge[newnode()]=Edge(a,b,num,tope[a]);
			tope[a]=cnt;
		}
		void twoadd_none(int a,int b,int num=0)
		{
			addedge(a,b,num);
			addedge(b,a,0);
		}
		void twoadd_yes(int a,int b,int num=0)
		{
			addedge(a,b,num);
			addedge(b,a,num);
		}
		int other(int x)
		{
			if(x%2)
			{
				return x+1;
			}
			return x-1;
		}
};
namespace ZDL
{
	const int inf=1e16;
	class node
	{
		public:
			int deep;
			int now;
	};
	int n;
	int start,end;
	vector<node> th;
	Road *road;
	bool bfs()
	{
		for(int i=0;i<=n;i++)
		{
			th[i].deep=inf;
			th[i].now=(*road).tope[i];
		}
		queue<int> q;
		th[start].deep=0;
		q.push(start);
		for(;q.size();)
		{
			int t=q.front();
			q.pop();
			for(int i=(*road).tope[t];i;i=(*road).edge[i].nxt)
			{
				int to=(*road).edge[i].to;
				if((*road).edge[i].num>0&&th[to].deep==inf)
				{
					q.push(to);
					th[to].deep=th[t].deep+1;
				}
			}
		}
		return th[end].deep<inf;
	}
	int dfs(int w,int sum)
	{
		if(w==end||!sum)
		{
			return sum;
		}
		int flow=0;
		for(int i=th[w].now;i&&sum;i=(*road).edge[i].nxt)
		{
			th[w].now=i;
			int to=(*road).edge[i].to;
			if((*road).edge[i].num>0&&th[to].deep==th[w].deep+1)
			{
				int use=dfs(to,min(sum,(*road).edge[i].num));
				if(use)
				{
					(*road).edge[i].num-=use;
					(*road).edge[(*road).other(i)].num+=use;
					sum-=use;
					flow+=use;
				}else
				{
					th[to].deep=inf;
				}
			}
		}
		return flow;
	}
	int solve(Road *_road,int _n,int _start,int _end)
	{
		start=_start;end=_end;
		n=_n;
		th=vector<node>(n+1);
		road=_road;
		int flow=0;
		for(;bfs();)
		{
			flow+=dfs(start,inf);
		}
		return flow;
	}
}
int n,m;
Road road;
void read()
{
	n=get_int();m=get_int();
	road.init(2*n+1,2*(m+2*n));
	int a,b;
	for(int i=1;i<=m;i++)
	{
		a=get_int();b=get_int();
		road.twoadd_none(a,b+n,1);
	}
}
vector<int> match;
void dfs(int w,vector<bool> &tag)
{
	tag[w]=1;
	for(int i=road.tope[w];i;i=road.edge[i].nxt)
	{
		int to=road.edge[i].to;
		if(to<1||to>2*n)
		{
			continue;
		}
		if(match[to]!=w&&!tag[match[to]])
		{
			dfs(match[to],tag);
		}
	}
}
int solve()
{
	int st=0,en=2*n+1;
	for(int i=1;i<=n;i++)
	{
		road.twoadd_none(st,i,1);
		road.twoadd_none(i+n,en,1);
	}
	ZDL::solve(&road,2*n+1,st,en);
	match=vector<int>(2*n+1);
	for(int i=1;i<=road.cnt;i++)
	{
		int a=road.edge[i].st,b=road.edge[i].to;
		if(a>=1&&a<=n&&b>=n+1&&b<=2*n&&road.edge[i].num==0)
		{
			match[a]=b;match[b]=a;
		}
	}
	
	vector<bool> tag(2*n+1);
	for(int i=1;i<=2*n;i++)
	{
		if(!match[i]&&!tag[i])
		{
			dfs(i,tag);
		}
	}
	ll sl=0,sr=0;
	for(int i=1;i<=n;i++)
	{
		sl+=tag[i];
		sr+=tag[i+n];
	}
	return sl*sr;
}
signed main()
{
//	freopen("t.txt","r",stdin);
	int t;
	t=get_int();
	for(;t;t--)
	{
		read();
		out_int(solve());putchar('\n');
	}
}