#include<bits/stdc++.h>
#ifdef xay5421
#define D(...) fprintf(stderr,__VA_ARGS__)
#define DD(...) D(#__VA_ARGS__ "="),debug_helper::debug(__VA_ARGS__),D("\n")
#include"/home/xay5421/debug.hpp"
#else
#define D(...) ((void)0)
#define DD(...) ((void)0)
#endif
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define each(x,v) for(auto&x:v)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
template<class T>void rd(T&x){int f=0,c;while(!isdigit(c=getchar()))f^=!(c^45);x=(c&15);while(isdigit(c=getchar()))x=x*10+(c&15);if(f)x=-x;}
template<class T>void pt(T x,int c=-1){if(x<0)putchar('-'),x=-x;if(x>9)pt(x/10);putchar(x%10+48);if(c!=-1)putchar(c);}
using namespace std;
using LL=long long;
using ULL=unsigned long long;
const int N=200005;
int T,n,m;
int st[N],dfn[N],low[N],top,idx,sz[N];
vector<int>e[N];
LL ans;
void solve(vector<int>&v){
	/*vector<LL>k(SZ(v)+1),b(SZ(v)+1);
	auto add=[&](int l,int r,int k0,int b0){
		DD(l,r,k0,b0);
		if(l<=r){
			k[l]+=k0;
			b[l]+=b0;
			k[r+1]-=k0;
			b[r+1]-=b0;
		}else{
			k[l]+=k0;
			b[l]+=b0;
			k[SZ(v)]-=k0;
			b[SZ(v)]-=b0;
			
			k[0]+=k0;
			b[0]+=b0+1LL*k0*SZ(v);
			k[r+1]-=k0;
			b[r+1]-=b0+1LL*k0*SZ(v);
		}
	};
	rep(i,0,SZ(v)-1){
		int p=(i+SZ(v)/2)%SZ(v);
		add(i,p,v[i],-1LL*v[i]*i);
		int q=(p+1)%SZ(v);
		int dq=(i-q+SZ(v))%SZ(v);
		int wq=1LL*v[i]*dq;
		add(q,i,-v[i],wq+1LL*q*v[i]);
	}
	rep(i,1,SZ(v))k[i]+=k[i-1],b[i]+=b[i-1];
	rep(i,0,SZ(v)-1)ans+=(k[i]*i+b[i])*v[i];*/
	int pos=0,cur=v[0],rem=n/2;
	while(rem){
		int t=min(cur,rem);
		cur-=t,rem-=t;
		if(!cur)pos=(pos+1)%SZ(v),cur=v[pos];
	}
	rep(i,0,SZ(v)-1){
		rem=v[i];
		while(rem){
			int t=min(cur,rem);
			ans+=1LL*t*min((i-pos+SZ(v))%SZ(v),(pos-i+SZ(v))%SZ(v));
			cur-=t,rem-=t;
			if(!cur)pos=(pos+1)%SZ(v),cur=v[pos];
		}
	}
}
void tarjan(int k1){
	sz[k1]=1;
	st[++top]=k1,dfn[k1]=low[k1]=++idx;
	for(auto&x:e[k1]){
		if(!dfn[x]){
			tarjan(x),low[k1]=min(low[k1],low[x]);
			
			if(low[x]>=dfn[k1]){
				vector<int>v;
				int sum=0;
				do{
					v.pb(sz[st[top]]),sz[k1]+=sz[st[top]];
					sum+=sz[st[top]];
				}while(st[top--]!=x);
				v.pb(n-sum);
				solve(v);
				// DD(v,ans);
			}
		}
		else{
			low[k1]=min(low[k1],dfn[x]);
		}
	}
}
int main(){
#ifdef xay5421
	freopen("a.in","r",stdin);
#endif
	rd(T);
	while(T--){
		rd(n),rd(m);
		rep(i,1,n)e[i].clear();
		rep(i,1,m){
			int u,v;
			rd(u),rd(v);
			e[u].pb(v),e[v].pb(u);
		}
		ans=0;
		top=0,idx=0;
		rep(i,1,n)dfn[i]=0,sz[i]=0;
		tarjan(1);
		printf("%lld\n",ans>>1);
	}
	return 0;
}