#include <bits/stdc++.h>
using namespace std;

#define il inline
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
using namespace std;
const int inf=1e9;
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
il int read(){
    char c=getchar();int z=0,f=1;
    while(c!='-'&&(c>'9'||c<'0')) c=getchar();
    if(c=='-') f=-1,c=getchar();
    while(c>='0'&&c<='9') z=(z<<1)+(z<<3)+c-'0',c=getchar();
    return z*f;
}

const long long N = 4e5 + 10;
const long long M = 1e6 + 10;
struct edge{
	int from, to;
	long long w;
}eg[M << 1];
int front[N], num;
void add(int x, int y, long long w){
	eg[++ num] = (edge){front[x], y, w};
	front[x] = num;
}
void ADD(int x, int y, long long w){
	add(x, y, w); add(y, x, 0);
}
int n, m, s, t;
int _front[N], dis[N];
bool bfs(){
	queue<int>q;
	q.push(s);
	memset(dis, 0, (t + 1) * sizeof(int));
	dis[s] = 1;
	while(!q.empty()){
		int o = q.front();
		q.pop();
		for (int i = front[o]; i; i = eg[i].from){
			int to = eg[i].to;
			if(dis[to] == 0 && eg[i].w){
				dis[to] = dis[o] + 1;
				q.push(to);
			}
		}
	}
	return dis[t] != 0;
}
long long dfs(int o, long long lim){
	if (o == t) return lim;
	long long mins = 0;
	for (int &i = _front[o]; i; i = eg[i].from){
		int to = eg[i].to;
		if(eg[i].w == 0 || dis[to] != dis[o] + 1)continue;
		long long now = dfs(to, min(lim - mins, eg[i].w));
		if(now == 0) dis[to] = 0;
		eg[i].w -= now;
		eg[((i - 1) ^ 1) + 1].w += now;
		mins += now;
		if(mins == lim)break;
	}
	return mins;
}
long long dinic(){
	long long re = 0;
	while(bfs()){
		memcpy(_front, front, (t + 1) * sizeof(int));
		re += dfs(s, 2e9);
	}
	return re;
}

int vis[N];
void solve(){
	n = read(), m = read();
	s = 2 * n + 1;
	t = s + 1;
	
	num = 0; 
	memset(front, 0, (t + 1) * sizeof(int));
	
	for (int i = 1; i <= m; ++ i){
		int x = read(), y = read();
		ADD(x, y + n, 1);
	}
	for (int i = 1; i <= n; ++ i) ADD(s, i, 1), ADD(i + n, t, 1);
	
	dinic();
	long long L = 0, R = 0;
	queue<int> q;
	
	memset(vis, 0, (t + 1) * sizeof(int));
	q.push(s);
	vis[s] = 1;
	while(!q.empty()){
		int o = q.front(); q.pop();
		for (int i = front[o]; i; i = eg[i].from){
			int to = eg[i].to;
			if(eg[i].w == 0 || vis[to]) continue;
			L += (1 <= to && to <= n);
			vis[to] = 1;
			q.push(to);
		}
	}
	
	memset(vis, 0, (t + 1) * sizeof(int));
	q.push(t);
	vis[t] = 1;
	while(!q.empty()){
		int o = q.front(); q.pop();
		for (int i = front[o]; i; i = eg[i].from){
			int to = eg[i].to;
			if(eg[i].w || vis[to]) continue;
			R += (1 + n <= to && to <= n + n);
			vis[to] = 1;
			q.push(to);
		}
	}
	
	printf("%lld\n", L * R);
}
int main(){
//	freopen("1.txt", "r", stdin);
//	freopen("2.txt", "w", stdout);
	int T; T = read();
	while(T --)solve();
}
/*
1
3 2
1 2
1 2

*/