#include<bits/stdc++.h>
#define int long long
using namespace std;

int Siz[51051],MaxSonSize[51051],zx1,zx2,t,g1sz,g2sz,ans,u[51051],v[51051],uu,vv,n;
void zxdfs(int x,int fa,vector<int>g[],int id){
	Siz[x]=1;MaxSonSize[x]=0;
	for(auto v:g[x]){
		if(v==fa)continue;
		zxdfs(v,x,g,id);
		Siz[x]+=Siz[v];MaxSonSize[x]=max(MaxSonSize[x],Siz[v]);
	}
	MaxSonSize[x]=max(MaxSonSize[x],(id==1?g1sz:g2sz)-Siz[x]);
	if(MaxSonSize[x]<=(id==1?g1sz:g2sz)/2){
		if(!zx1)zx1=x;
		else if(!zx2)zx2=x;
	}
}

vector<int>g[51051];
vector<int>g1[51051],g2[51051];

void dfs(int x,int fa,int id){
	if(id==1)g1sz++;
	else g2sz++;
	for(auto to:g[x]){
		if(to==fa)continue;
		if((x==uu&&to==vv)||(x==vv&&to==uu))continue;
		if(id==1){
			g1[x].push_back(to);g1[to].push_back(x);
		}else{
			g2[x].push_back(to);g2[to].push_back(x);
		}
		dfs(to,x,id);
	}
}

signed main(){
	freopen("centroid.in","r",stdin);freopen("centroid.out","w",stdout);
	cin>>t;
	while(t--){ans=0;
		cin>>n;
		for(int i=1;i<=n;i++){
			g[i].clear();g1[i].clear();g2[i].clear();
		}
		for(int i=1;i<=n-1;i++){
			cin>>u[i]>>v[i];
			g[u[i]].push_back(v[i]);
			g[v[i]].push_back(u[i]);
		}
		for(int br=1;br<=n-1;br++){
			memset(Siz,0,sizeof(Siz));memset(MaxSonSize,0,sizeof(MaxSonSize));
			for(int i=1;i<=n;i++){
				g1[i].clear();g2[i].clear();
			}
			zx1=0;zx2=0;g1sz=0;g2sz=0;
			uu=u[br],vv=v[br];
			dfs(uu,0,1);dfs(vv,0,2);
			zxdfs(uu,0,g1,1);
			ans+=zx1+zx2;zx1=0;zx2=0;
			memset(Siz,0,sizeof(Siz));memset(MaxSonSize,0,sizeof(MaxSonSize));
			zxdfs(vv,0,g2,2);
			ans+=zx1+zx2;zx1=0;zx2=0;
		}
		cout<<ans<<"\n";
	}
	return 0;
}