bool M1;
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define LL __int128
#define db double
#define LD long double
#define Pii pair<int,int>
#define Pll pair<ll,ll>
#define Pull pair<ull,ull>
#define Pdb pair<db,db>
#define fir first
#define sec second
#define vec vector<int>
#define pb push_back
#define qlr cerr<<"qlr\n"
#define dyh cerr<<"dyh\n"
#define pc(x) __builtin_popcount(x)
#define uni(x,y) uniform_int_distribution<int>(x,y)(rng)
#define unl(x,y) uniform_int_distribution<ll>(x,y)(rng)
#define unr(x,y) uniform_real_distribution<double>(x,y)(rng)
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define UF(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define look_memory cerr<<'\n'<<abs(&M1-&M2)/1024.0/1024<<'\n'
#define look_time cerr<<'\n'<<clock()*1.0/CLOCKS_PER_SEC<<'\n'
mt19937 rng(time(0)^(*new int));
const int INF=0x3f3f3f3f;
const int Mod=998244353;
template<typename T>
inline void inc(T &a,T b){
	if(b<0) b+=Mod;
	a+=b;
	if(a>=Mod) a-=Mod;
}
template<typename T>
inline void dec(T &a,T b){
	if(b<0) b+=Mod;
	a-=b;
	if(a<0) a+=Mod;
}
template<typename T>
inline void muc(T &a,T b){
	a=a*b%Mod;
}
template<typename T>
inline bool chkmin(T &a,T b){
	if(a<=b) return false;
	a=b;
	return true;
}
template<typename T>
inline bool chkmax(T &a,T b){
	if(a>=b) return false;
	a=b;
	return true;
}
int T,n;
uint ans;
vec e[100010];
struct Dsu{
	#define N 100000
	int fa[N+10];
	void init(int n){
		F(i,1,n) fa[i]=i;
	}
	int fd(int x){
		return fa[x]==x?x:fa[x]=fd(fa[x]);
	}
	void merge(int x,int y){
		x=fd(x),y=fd(y);
		fa[x]=y;
	}
	#undef N
}dsu;
struct Tree{
	#define N 100000
	int n,rt;
	int fth[N+10],siz[N+10],son[N+10],top[N+10],dfn[N+10];
	vec e[N+10];
	void dfs1(int u,int fa){
		fth[u]=fa;
		siz[u]=1;
		son[u]=0;
		for(auto v:e[u]){
			if(v==fa) continue;
			dfs1(v,u);
			siz[u]+=siz[v];
			if(siz[v]>siz[son[u]]) son[u]=v;
		}
	}
	void dfs2(int u,int fa,int topf){
		top[u]=topf;
		dfn[u]=++dfn[0];
		if(son[u]) dfs2(son[u],u,topf);
		for(auto v:e[u]){
			if(v==fa||v==son[u]) continue;
			dfs2(v,u,v);
		}
	}
	void build(){
		dfs1(rt,0);
		dfs2(rt,0,rt);
		dfn[0]=0;
	}
	vec get_chain(int x){
		vec res;
		while(x){
			res.pb(x);
			x=son[x];
		}
		return res;
	}
	#undef N
}T1,T2;
struct Seg{
	#define N 100000
	#define ls k*2
	#define rs k*2+1
	uint a[N+10];
	uint w1[N*4+10],w2[N*4+10],w3[N*4+10],tag[N*4+10];//b,a*c,a*b*c
	void update(int k){
		w1[k]=w1[ls]+w1[rs];
		w2[k]=w2[ls]+w2[rs];
		w3[k]=w3[ls]+w3[rs];
	}
	void down(int k){
		if(tag[k]){
			w1[ls]+=tag[k];
			w3[ls]+=w2[ls]*tag[k];
			tag[ls]+=tag[k];
			w1[rs]+=tag[k];
			w3[rs]+=w2[rs]*tag[k];
			tag[rs]+=tag[k];
			tag[k]=0;
		}
	}
	void build(int k,int L,int R){
		w1[k]=0,w2[k]=0,tag[k]=0;
		if(L==R) return;
		int mid=(L+R)>>1;
		build(ls,L,mid);
		build(rs,mid+1,R);
	}
	void change1(int k,int L,int R,int x,int y){
		if(L==R){
			w2[k]=a[L]*y;
			w3[k]=w1[k]*w2[k];
			return;
		}
		down(k);
		int mid=(L+R)>>1;
		if(x<=mid) change1(ls,L,mid,x,y);
		else change1(rs,mid+1,R,x,y);
		update(k);
	}
	void change2(int k,int L,int R,int x,int y,int z){
		if(L>=x&&R<=y){
			w3[k]+=w2[k]*z;
			tag[k]+=z;
			return;
		}
		down(k);
		int mid=(L+R)>>1;
		if(x<=mid) change2(ls,L,mid,x,y,z);
		if(y>mid) change2(rs,mid+1,R,x,y,z);
		update(k);
	}
	uint query(int k,int L,int R,int x,int y){
		if(L>=x&&R<=y) return w3[k];
		down(k);
		int mid=(L+R)>>1;
		if(y<=mid) return query(ls,L,mid,x,y);
		else if(x>mid) return query(rs,mid+1,R,x,y);
		else return query(ls,L,mid,x,y)+query(rs,mid+1,R,x,y);
	}
	#undef N
	#undef ls
	#undef rs
}seg;
void add(int x){
	seg.change1(1,1,n,T2.dfn[x],1);
	while(x){
		seg.change2(1,1,n,T2.dfn[T2.top[x]],T2.dfn[x],1);
		x=T2.fth[T2.top[x]];
	}
}
void del(int x){
	seg.change1(1,1,n,T2.dfn[x],0);
	while(x){
		seg.change2(1,1,n,T2.dfn[T2.top[x]],T2.dfn[x],-1);
		x=T2.fth[T2.top[x]];
	}
}
void dfs1(int u,int fa){
	add(u);
	for(auto v:T1.e[u]){
		if(v==fa) continue;
		dfs1(v,u);
	}
}
void dfs2(int u,int fa){
	del(u);
	for(auto v:T1.e[u]){
		if(v==fa) continue;
		dfs2(v,u);
	}
}
uint query(int x){
	uint res=0;
	while(x){
		res+=seg.query(1,1,n,T2.dfn[T2.top[x]],T2.dfn[x]);
		x=T2.fth[T2.top[x]];
	}
	return res;
}
void solve(){
	cin>>n;
	F(i,1,n) e[i].clear();
	F(i,1,n-1){
		int x,y;
		cin>>x>>y;
		e[x].pb(y);
		e[y].pb(x);
	}
	T1.n=n,T1.rt=1;
	F(i,1,n) T1.e[i].clear();
	dsu.init(n);
	UF(i,n,1){
		for(auto j:e[i]){
			if(j<i) continue;
			T1.e[i].pb(dsu.fd(j));
			dsu.merge(j,i);
		}
	}
	T2.n=n,T2.rt=n;
	F(i,1,n) T2.e[i].clear();
	dsu.init(n);
	F(i,1,n){
		for(auto j:e[i]){
			if(j>i) continue;
			T2.e[i].pb(dsu.fd(j));
			dsu.merge(j,i);
		}
	}
	T1.build();
	T2.build();
	ans=0;
	F(i,1,n) seg.a[T2.dfn[i]]=i;
	seg.build(1,1,n);
	F(i,1,n){
		if(T1.top[i]!=i) continue;
		vec V=T1.get_chain(i);
		reverse(V.begin(),V.end());
		for(auto j:V){
			add(j);
			for(auto k:T1.e[j]){
				if(k!=T1.fth[j]&&k!=T1.son[j]) dfs1(k,j);
			}
			ans+=j*query(j);
		}
		for(auto j:V){
			del(j);
			for(auto k:T1.e[j]){
				if(k!=T1.fth[j]&&k!=T1.son[j]) dfs2(k,j);
			}
		}
	}
	cout<<ans<<'\n';
}
bool M2;
int main(){
//	freopen("ex_a4.in","r",stdin);
//	freopen("monotone.out","w",stdout);
	srand(time(0)^(*new int));
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>T;
	while(T--) solve();
	look_memory;
	look_time;
	return 0;
}
/*
1
3
1 3
2 3

6
3
1 2
2 3
3
1 3
2 3
7
2 1
3 1
4 1
5 1
6 5
7 6
6
2 1
3 1
4 1
5 4
6 1
9
2 1
3 2
4 3
5 1
6 4
7 5
8 2
9 3
9
2 1
3 2
4 3
5 4
6 5
7 2
8 3
9 5
*/