#include "bits/stdc++.h"
using namespace std;
const int Len = 1e5 + 5 , Inf = 1e9;
int S,T,n,m,head[Len],cnt = 1,cur[Len],flag[Len],dep[Len];
struct node
{
	int next,to,w;
}edge[Len << 1];
inline void add(int from,int to,int w)
{
	edge[++ cnt].to = to;
	edge[cnt].w = w;
	edge[cnt].next = head[from];
	head[from] = cnt;
}
inline void adeg(int from,int to,int w){add(from , to , w) , add(to , from , 0);}
inline int BFS()
{
	queue<int> Q;
	for(int i = 1 ; i <= T ; i ++) cur[i] = flag[i] = dep[i] = 0;
	dep[S] = 1 , cur[S] = head[S] , Q.push(S);
	while(!Q.empty())
	{
		int p = Q.front();Q.pop();
		for(int e = head[p] ; e ; e = edge[e].next)
		{
			int to = edge[e].to;
			if(edge[e].w && !dep[to])
			{
				dep[to] = dep[p] + 1;
				cur[to] = head[to];
				Q.push(to);
				if(to == T) return 1;
			}
		}
	}
	return 0;
}
int dfs(int u,int In)
{
	if(u == T) return In;
	flag[u] = 1;
	int Out = 0;
	for(int e = cur[u] ; e && In > 0 ; e = edge[e].next)
	{
		cur[u] = e;
		int to = edge[e].to;
		if(edge[e].w && dep[to] == dep[u] + 1 && !flag[to])
		{
			int res = dfs(to , min(In , edge[e].w));
			In -= res;
			Out += res;
			edge[e].w -= res;
			edge[e ^ 1].w += res;
		}
	}
	flag[u] = 0;
	if(!Out) dep[u] = -1;
	return Out;
}
int ct1,ct2;
struct seg
{
	int u,v;
	seg(){u = v = 0;}
	seg(int U,int V){u = U , v = V;}
}sg[Len << 2];int M;
inline void BFS1()
{
	queue<int> Q;
	Q.push(S);for(int i = 1 ; i <= T ; i ++) flag[i] = 0;
	while(!Q.empty())
	{
		int p = Q.front();Q.pop();
		for(int e = head[p] ; e ; e = edge[e].next)
		{
			int to = edge[e].to;
			if(flag[to] || !edge[e].w) continue;
			if(to <= n) ct1 ++;
			Q.push(to);
			flag[to] = 1;
		}
	} 
}
inline void BFS2()
{
	queue<int> Q;M = 0;
	for(int i = 1 ; i <= T ; i ++)
	{
		flag[i] = 0;
		for(int e = head[i] ; e ; e = edge[e].next)
		{
			int to = edge[e].to;
			if(edge[e].w) sg[++ M] = seg(to , i);
		}
	}
	cnt = 0;for(int i = 1 ; i <= T ; i ++) head[i] = 0;
	for(int i = 1 ; i <= M ; i ++) add(sg[i].u , sg[i].v , 0);
	Q.push(T);
	while(!Q.empty())
	{
		int p = Q.front();Q.pop();
		for(int e = head[p] ; e ; e = edge[e].next)
		{
			int to = edge[e].to;
			if(flag[to]) continue;
			if(n + 1 <= to && to <= (n << 1)) ct2 ++;
			Q.push(to);
			flag[to] = 1;
		}
	} 
}
signed main()
{
	int TT;scanf("%d",&TT);
	for(int lll = 1 ; lll <= TT ; lll ++)
	{
		scanf("%d %d",&n,&m);ct1 = ct2 = 0;S = (n << 1) + 1 , T = S + 1;
		for(int i = 1 ; i <= m ; i ++) 
		{
			int x,y;scanf("%d %d",&x,&y);
			adeg(x , y + n , 1);
		}
		for(int i = 1 ; i <= n ; i ++) adeg(S , i , 1) , adeg(i + n , T , 1);
		int as = 0;while(BFS()) as += dfs(S , Inf);
		BFS1();BFS2();
		printf("%lld\n",1ll * ct1 * ct2);
		for(int i = 1 ; i <= T ; i ++) head[i] = 0;cnt = 1;
	}
	return 0;
}