#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+5;
struct edge{
	int v,nxt;
}e[N<<1];
int head[N],cnt;
void add(int u,int v){
	e[++cnt]={v,head[u]},head[u]=cnt;
}
int n,deg[N],dep[N],sz[N],big[N],secbig[N],fa[N],dfnl[N],dfnr[N],times;
void dfs0(int u,int F){
	sz[u]=1,dep[u]=dep[F]+1,big[u]=secbig[u]=0;
	dfnl[u]=++times;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(v!=F){
			fa[v]=u,dfs0(v,u);
			sz[u]+=sz[v];
			if(sz[v]>sz[big[u]])big[u]=v;
			else if(sz[v]>sz[secbig[u]])secbig[u]=v;
		}
	}
	dfnr[u]=times;
}
namespace llt{
    vector<int> a;
    void dfs1(int u,int pre){
    	a.push_back(u);
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].v;
            if(v!=pre)dfs1(v,u);
        }
    }
	void solve(){
		int st;
        for(int i=1;i<=n;++i){
            if(deg[i]==1)st=i;
        }
		// cout<<st<<'\n';
		a.clear();
        dfs1(st,0);
        ll res=0;
        for(int i=0;i<n-1;++i){
            if(i%2==1)res+=a[i/2]+a[i/2+1];
            else res+=a[i/2];
			++i;
			if((n-i)%2==1)res+=a[n-1-(n-1-i)/2];
			else res+=a[n-1-(n-1-i)/2]+a[n-1-(n-1-i)/2-1];
			--i;
        }
        cout<<res<<'\n';
	}
};
int U[N],V[N];
typedef pair<int,int> pii;
bool in(int u,int v){	// whether u in subtree(v)
	return dfnl[v]<=dfnl[u]&&dfnl[u]<=dfnr[v];
}
namespace gen{
	int W[N],secW[N],mins[N];
	void solve(){
		ll res=0;
		for(int i=1;i<=n;++i)mins[i]=2e9,W[i]=secW[i]=0;
		for(int u=1;u<=n;++u){
			for(int v=u;v!=0;v=fa[v]){
				int k=max(sz[big[u]],sz[v]-sz[u]);
				if(k<mins[v])mins[v]=k,W[v]=u,secW[v]=0;
				else if(k==mins[v])secW[v]=u;
			}
		}
		for(int k=1;k<n;++k){
			int u=U[k],v=V[k];
			if(dep[u]>dep[v])swap(u,v); res+=W[v]+secW[v];
			//cout<<"out of "<<v<<" "<<w<<' '<<secww<<'\n';
			int del=sz[v];
			sz[v]-=del;
			vector<pii> Upd;
			for(int w=fa[v];w!=0;w=fa[w]){
				sz[w]-=del;
				if(sz[big[w]]<sz[secbig[w]]||big[w]==v)Upd.push_back({w,big[w]}),big[w]=secbig[w];
			}
			int minS=2e9,ww,secww=0;
			for(int w=1;w!=0;w=big[w]){
				int maxS=0;
				for(int i=head[w];i;i=e[i].nxt){
					int p=e[i].v;
					if(p!=fa[w]&&!in(p,v))maxS=max(maxS,sz[p]);
				}
				maxS=max(maxS,n-del-sz[w]);
				if(maxS<minS)ww=w,minS=maxS;
				else if(maxS==minS)secww=w;
			}
			for(int w=v;w!=0;w=fa[w])sz[w]+=del;
			for(pii p:Upd)big[p.first]=p.second;
			res+=ww+secww;
			Upd.clear();
		}
		cout<<res<<'\n';
		memset(W,0,sizeof W);
		memset(secW,0,sizeof secW);
		memset(mins,0,sizeof mins);
	}
};
signed main() {
	ios :: sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int T;cin>>T;
	while(T--){
		cin>>n;
		for(int i=1;i<n;++i){
			int u,v;cin>>u>>v; U[i]=u,V[i]=v;
			add(u,v),add(v,u);
			++deg[u],++deg[v];
		}
		dfs0(1,0);
		int cnt1=0,cnt2=0;
		for(int i=1;i<=n;++i)cnt1+=(deg[i]==1),cnt2+=(deg[i]==2);
		if(cnt1==2&&cnt2==n-2)llt::solve();
		else gen::solve();
		memset(e,0,sizeof e);
		memset(head,0,sizeof head); cnt=0;
		memset(deg,0,sizeof deg);
		memset(dep,0,sizeof dep);
		memset(sz,0,sizeof sz);
		memset(big,0,sizeof big);
		memset(secbig,0,sizeof secbig);
		memset(fa,0,sizeof fa);
	memset(dfnl,0,sizeof dfnl);
	memset(dfnr,0,sizeof dfnr);
	times=0;
		// for(int i=1;i<=n;++i)head[i]=deg[i]=dfnl[i]=dfnr[i]=dep[i]=fa[i]=big[i]=secbig[i]=sz[i]=0; cnt=times=0;
	}
	return 0;
}