// what is matter? never mind. 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define ull unsigned long long
#define int long long
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define mod 2013265921
struct modint{
	unsigned int x;
	modint(unsigned int o=0){x=o;}
	modint &operator = (unsigned int o){return x=o,*this;}
	modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
	modint &operator -=(modint o){return x=x<o.x?x-o.x+mod:x-o.x,*this;}
	modint &operator *=(modint o){return x=1ll*x*o.x%mod,*this;}
	modint &operator ^=(unsigned int b){
		modint a=*this,c=1;
		for(;b;b>>=1,a*=a)if(b&1)c*=a;
		return x=c.x,*this;
	}
	modint &operator /=(modint o){return *this *=o^=mod-2;}
	friend modint operator +(modint a,modint b){return a+=b;}
	friend modint operator -(modint a,modint b){return a-=b;}
	friend modint operator *(modint a,modint b){return a*=b;}
	friend modint operator /(modint a,modint b){return a/=b;}
	friend modint operator ^(modint a,unsigned int b){return a^=b;}
	friend bool operator ==(modint a,modint b){return a.x==b.x;}
	friend bool operator !=(modint a,modint b){return a.x!=b.x;}
	bool operator ! () {return !x;}
	modint operator - () {return x?mod-x:0;}
	bool operator <(const modint&b)const{return x<b.x;}
};
inline modint qpow(modint x,unsigned int y){return x^y;}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 400005
#define inf 0x3f3f3f3f

int n,m;
vector<int>e[maxn];
vi g[maxn];

int cnt;
int dfn[maxn],low[maxn],stk[maxn],tp,idx,bel[maxn],fa[maxn];
void tar(int u,int pa)
{
	dfn[u]=low[u]=++idx,stk[++tp]=u;
	for(auto v:e[u]){
		if(v==pa)continue;
		if(!dfn[v]){
			tar(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]){
				++cnt; int x; 
				g[u].pb(cnt); fa[cnt]=u;// cout<<"addg "<<u<<' '<<cnt<<endl;
				fa[cnt]=u;
				do{
					x=stk[tp--];
					g[cnt].pb(x),bel[x]=cnt; //cout<<"addg "<<cnt<<" "<<x<<endl;
					fa[x]=cnt;
				}while(x!=v);
			}
		}
		else low[u]=min(low[u],dfn[v]);
	}
}

int res;

namespace S{
	int a[maxn],n;
	pii b1[maxn],b2[maxn];
	int n1,n2;
	int solve(){
		int res=0;
		if(n==2){
			res+=min(a[1],a[2]);
			return res;
		}
		int rs=::n/2;
		n1=n2=0;
		For(i,1,n){
			int t=min(rs,a[i]);
			if(!t)continue;
			b1[++n1]=mkp(t,i-1);
			rs-=t;a[i]-=t;
			if(!rs)break;
		}
		For(i,1,n)if(a[i])b2[++n2]=mkp(a[i],i-1);
		auto calc=[&](int x,int y){
			int t=abs(x-y);
			return min(t,n-t);
		};
		while(n1||n2){
			while(n1&&!b1[n1].fi)--n1;
			while(n2&&!b2[n2].fi)--n2;
			if(!n1&&!n2)break;
			int t=min(b1[n1].fi,b2[n2].fi);
			res+=t*calc(b1[n1].se,b2[n2].se);
			b1[n1].fi-=t;
			b2[n2].fi-=t;
		}
		return res;
	}
}

int sz[maxn];
void dfs(int u){
	sz[u]=(u<=n);
	for(int v:g[u]) dfs(v),sz[u]+=sz[v];
	if(u>n){
		S::n=0;
		for(int v:g[u]) S::a[++S::n]=sz[v];
		S::a[++S::n]=n-sz[u];
		res+=S::solve();
	}
}

void work()
{
	n=read(),m=read();
	cnt=n; res=0;
	For(i,0,n*2) e[i].clear(),g[i].clear(),dfn[i]=low[i]=bel[i]=sz[i]=fa[i]=0; tp=idx=0;
	For(i,1,m){
		int u=read(),v=read();
		e[u].pb(v),e[v].pb(u);
	}
	tar(1,0);
	dfs(1);
	cout<<res<<"\n";
}

signed main()
{
	int T=read();
	while(T--)work();
	return 0;
}
/*

10
4 2 2 2 0 0 1 1 3 3
1 4 0 4 2 2 3 3 0 0
2 0 1 0 3 3 4 4 1 1
2 0 1 0 3 3 4 4 1 1
2 0 1 0 3 3 4 4 1 1
4 2 3 2 0 0 1 1 3 3
3 1 2 1 4 4 0 0 2 2
3 1 2 1 4 4 0 3 2 2
1 4 0 4 2 2 3 3 0 0
1 4 0 4 2 2 3 3 0 0
*/