#include<bits/stdc++.h>
using namespace std;
const int N=6e5+10;
int e[N],ne[N],h[N],p[N],f[N][20],g[N][20],sz[N];
long long ans=0,n,idx=0;
inline void add(int a,int b){
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx++;
} 
inline void cst(int u,int son){
	f[u][0]=son;
	for(int i=1;i<19;i++){
		f[u][i]=f[f[u][i-1]][i-1];
	}
}
inline void cans(int &u){
	int tot=sz[u];
	for(int i=18;i>=0;i--){
		if(f[u][i]&&tot-sz[f[u][i]]<=tot/2){
			u=f[u][i];
		}
	}
	ans+=u;
	if(tot%2==0&&sz[u]==tot/2) ans+=p[u];
}
inline void dfs1(int u,int father){
    sz[u]=1,p[u]=father;
    int son=0;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==father) continue;
        dfs1(j,u);
        sz[u]+=sz[j];
        if(sz[j]>sz[son]) son=j;
    }
   cst(u,son);
}
inline void dfs(int u,int father){
	int s1=0,s2=0,szu=sz[u];
	for(int i=h[u];~i;i=ne[i]){
		int j=e[i];
		if(j==father) continue;
		if(sz[j]>=sz[s1]) s2=s1,s1=j;
		else if(sz[j]>sz[s2]) s2=j;
 	}
 	for(int i=h[u];~i;i=ne[i]){
 		int j=e[i];
 		if(j==father) continue;
 		cans(j);
 		p[u]=j;
 		sz[u]=n-sz[j];
 		if(j!=s1) cst(u,s1);
 		else cst(u,s2);
 		cans(u);
 		dfs(j,u);
	 }
	 p[u]=father,sz[u]=szu;
	 memcpy(f[u],g[u],sizeof g[u]);
}
int main(){
	int t;
	cin>>t;
	while(t--){
		cin>>n;
		memset(h,-1,sizeof h);
		memset(p,0,sizeof p);
		idx=0;
		ans=0;
		memset(sz,0,sizeof sz);
		for(int i=1;i<n;i++){
			int u,v;
			cin>>u>>v;
			add(u,v),add(v,u);
		}
		dfs1(1,-1);
		memcpy(g,f,sizeof f);
		dfs(1,-1);
		cout<<ans<<endl;
	}
	return 0;
}