#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+100;
struct aa{
	int v,w;
};
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
vector<int> g[N];
vector<aa> T[N],E[N];
bool ins[N],vis[N],inq[N];
int dfn[N],low[N],bel[N],siz[N],dcnt,deg[N],stk[N],tp,scnt;
void tarjan(int u){
	stk[++tp]=u,ins[u]=1,low[u]=dfn[u]=++dcnt;
	for(int i:g[u]){
		if(!dfn[i]){
			tarjan(i);
			low[u]=min(low[u],low[i]);
		}
		else if(ins[i])low[u]=min(low[u],low[i]);
	}
	if(low[u]==dfn[u]){
		++scnt;
		while(ins[u]==1)
			bel[stk[tp]]=scnt,++siz[scnt],ins[stk[tp--]]=0;
	}
}
aa mka(int x,int y){
	aa res;
	res.v=x,res.w=y;
	return res;
}
int w[N],fa[N];
void work(int x){
	inq[x]=vis[x]=1;
	for(aa i:T[x]){
		if(i.v==fa[x])continue;
		if(!vis[i.v]){
			fa[i.v]=x,w[i.v]=i.w;work(i.v);
		}
		else if(inq[i.v]){
			vector<aa> mp;
			for(int cur=x;cur!=i.v;cur=fa[cur])mp.push_back(mka(cur,w[cur]));
			mp.push_back(mka(i.v,i.w));
			bool bk=1;
			int st=0,en=0;
			int si=mp.size();
			for(int i=0;i<si;i++){
				if(mp[i].w!=mp[(i-1+si)%si].w){
					if(mp[i].w==0){
						if(st!=0)bk=0;
						st=mp[i].v;
					}else{
						if(en!=0)bk=0;
						en=mp[i].v;
					}
				}
			}
			//if(bk)cout<<st<<" ff "<<en<<endl;
			if(bk&&st&&en)E[st].push_back(mka(en,-1)),++deg[en];
		}
	}
	inq[x]=0;
}
int dp[N],ans;
void solve(){
	int n,m;
	n=read(),m=read();
	scnt=tp=dcnt=0;
	for(int i=1;i<=n;++i){
		T[i].clear(),E[i].clear(),g[i].clear();
		low[i]=dfn[i]=stk[i]=bel[i]=siz[i]=ins[i]=dp[i]=fa[i]=w[i]=deg[i]=inq[i]=vis[i]=0;
	}
	ans=0;
	for(int i=1;i<=m;i++){
		int u=read(),v=read();
		g[u].push_back(v);
	}
	for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i); 
	for(int i=1;i<=n;i++){
		for(int j:g[i]){
			int x=bel[i],y=bel[j];
			if(x==y)continue;
			T[x].push_back(mka(y,1));
			T[y].push_back(mka(x,0));
			E[x].push_back(mka(y,1));
			++deg[y];
		}
	}
	work(1);
	queue<int>q;
	//cout<<scnt<<" hh "<<endl;
	for(int i=1;i<=scnt;i++){
		if(!deg[i]){
			q.push(i);	
		//	cout<<i<<endl;
		}
		
	}
	for(int i=1;i<=scnt;++i)dp[i]=siz[i];
	while(!q.empty()){
		int u=q.front();
		q.pop();
		ans+=dp[u]*siz[u];
	//	cout<<u<<" g "<<ans<<endl;
		for(auto i:E[u]){
	//		cout<<i.v<<" gg "<<i.w<<endl;
			dp[i.v]+=dp[u]*i.w;
			if(!--deg[i.v])q.push(i.v);
		}
	}
	printf("%lld\n",ans);
}
signed main(){
	int t;
	cin>>t;
	while(t--)solve();
}