#include<bits/stdc++.h>
#define ll long long
#define N 300500
using namespace std;
int T,n,a,b;

int head[N],cnt;
struct Edge{int to,next;}edge[N];
void add(int u,int v){
	edge[++cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt;
}

int tree1[N],tree2[N];
inline void update(int x,int v,int tree[]){
	if(x==0)	return;
	for(int i=x;i<=n;i+=i&-i)	tree[i]+=v;
}
inline int query(int x,int tree[]){
	int sum=0;for(int i=x;i;i-=i&-i)	sum+=tree[i];
	return sum;
}

int size[N],g[N],root,mins,rt;
void dfs1(int fa,int x)
{
	size[x]=1;	g[x]=0;
	for(int i=head[x];i;i=edge[i].next)
		if(edge[i].to!=fa){
			dfs1(x,edge[i].to);	size[x]+=size[edge[i].to];
			if(size[edge[i].to]>g[x])	g[x]=size[edge[i].to];
		}
	if(g[x]<n-size[x])	g[x]=n-size[x]; 
	if(g[x]<mins&&g[x])	root=x,mins=g[x];
}

ll ans;int u,v;bool heavy[N];
void dfs2(int fa,int x)
{
	update(n-size[fa],-1,tree1);
	update(size[fa],1,tree1);

	update(n-size[x],1,tree2);					//?

	if(heavy[fa])	heavy[x]=1;

	ans+=x*query(2*size[x],tree1);
	ans-=x*query(2*g[x]-1,tree1);

	ans+=x*query(2*size[x],tree2);
	ans-=x*query(2*g[x]-1,tree2);

	if(size[heavy[x]?u:v]*2+size[x]<=n)	ans+=rt;

	for(int i=head[x];i;i=edge[i].next)
		if(edge[i].to!=fa)	dfs2(x,edge[i].to);

	ans-=x*query(2*size[x],tree2);
	ans+=x*query(2*g[x]-1,tree2);

	update(n-size[fa],1,tree1);
	update(size[fa],-1,tree1);					//回溯
}


void clean(){
	ans=cnt=u=v=0;	mins=N;
	for(int i=0;i<=n;++i)	heavy[i]=tree1[i]=tree2[i]=head[i]=0;
}
int main()
{
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);	clean();
		for(int i=1;i<n;++i){
			scanf("%d%d",&a,&b);
			add(a,b),add(b,a);
		}
		dfs1(1,1);rt=root;	dfs1(rt,rt);
		for(int i=1;i<=n;++i)	update(n-size[i],1,tree1);
		for(int i=head[rt];i;i=edge[i].next){
			if(size[edge[i].to]>size[v])	v=edge[i].to;
			if(size[u]<size[v])	swap(u,v);
		}heavy[u]=1;
		for(int i=head[rt];i;i=edge[i].next)	dfs2(rt,edge[i].to);
		printf("%lld\n",ans);
	}
}