#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define vec(...) vector<__VA_ARGS__>
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}

// init(lhs size, rhs size)
// North America Division Championship 2020 C - Borders
// NERC 2022 D - Dominoes
struct kuhn{
	int n,m;
	vec(vi) g;
	vi usd;
	vi mt;
	void init(int _n,int _m){
		n=_n,m=_m;
		g=vec(vi)(n);
	}
	void add_edge(int u,int v){
		g[u].pb(v);
	}
	vec(pii) solve(){
		auto try_kuhn=[&](auto self,int v)->bool{
			if(usd[v]){
				return 0;
			}
			usd[v]=1;
			for(auto u:g[v]){
				if(mt[u]==-1 or self(self,mt[u])){
					mt[u]=v;
					return 1;
				}
			}
			return 0;
		};
		mt=vi(m,-1);
		rep(v,n){
			usd=vi(n,0);
			try_kuhn(try_kuhn,v);
		}
		vec(pii) ret;
		rep(v,m){
			ret.pb({mt[v],v});
		}
		return ret;
	}
};

struct dsu{
	int _n;
	vi si,par,leb;
	dsu(int n=0){
		init(n);
	}
	void init(int n=0){
		_n=n;
		par=vi(_n,0);
		si=vi(_n,0);
		leb=vi(_n,-1);
		rep(i,n){
			si[i]=1;
			par[i]=i;
		}	
	}
	int parent(int u){return par[u]=(par[u]==u?u:parent(par[u]));}
	bool same(int u,int v){return parent(u)==parent(v);}
	void merge(int u,int v){
		u=parent(u),v=parent(v);
		if(!same(u,v)){
			if(si[u]<si[v]) swap(u,v);
			leb[u]=max(leb[u],leb[v]);
			_n-=1;
			si[u]+=si[v];
			par[v]=u;
		}
	}
	int size(int v=-1){return v==-1?_n:si[parent(v)];}
};

void slv(){
	int n,m;
	cin>>n>>m;
	int n2=n*2;

	vec(vi) adj(n2);
	dsu uf(n2);
	kuhn g; g.init(n,n);
	rep(i,m){
		int u,v;
		cin>>u>>v;
		u-=1,v-=1;
		uf.merge(u,v+n);
		adj[u].pb(v+n),adj[v+n].pb(u);
		g.add_edge(u,v);
	}
	auto res=g.solve();

	vi mat(n2,-1);
	for(auto [x,y]:res){
		// print(x,y);
		if(x!=-1) mat[y+n]=x, mat[x]=y+n;
	}

	vec(vi) rs(n2);
	rep(v,n2) rs[uf.parent(v)].pb(v);

	int cnt_r=0,cnt_l=0;
	rep(x,n2){
		if(x<n){
			if(mat[x]==-1) cnt_l+=1;
		}else{
			if(mat[x]==-1) cnt_r+=1;
		}
	}

	int ans=0;
	int x=0,y=0;
	rep(v,n2){
		// if(v!=4) continue;
		// if(uf.parent(v)==v){
		// 	int lhs=0,u_lhs=0,rhs=0,u_rhs=0;
		// 	for(auto x:rs[v]){
		// 		if(x<n){
		// 			if(mat[x]==-1) u_lhs+=1;
		// 			else lhs+=1;
		// 		}else{
		// 			if(mat[x]==-1) u_rhs+=1;
		// 			else rhs+=1;
		// 		}
		// 	}
		// 	if(u_lhs>0) ans+=rhs*cnt_l;
		// 	if(u_rhs>0) ans+=lhs*cnt_r;
		// 	// print("~ ~ ~",v,lhs,rhs);
		// }
		// if(mat[v]==-1) continue;
		vi usd(n2);
		auto dfs=[&](auto self,int v)->bool{
			if(usd[v]) return false;
			usd[v]=1;
			int u=mat[v];
			// print(v,u);
			if(u==-1) return true;
			for(auto x:adj[u]){
				if(self(self,x)){
					return true;
				}
			}
			return false;
		};
		bool e=dfs(dfs,v);
		if(e){
			if(v<n) ans+=cnt_r;
			else ans+=cnt_l;
		}
	}
	// print(ans);
	ans-=cnt_l*cnt_r;
	print(ans);
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	int t;
	cin>>t;
	rep(cs,t){
		slv();
	}
}