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;
uint w1[100010],w2[100010];
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;
void add(int x){
	w1[T2.dfn[x]]=1;
	while(x){
		w2[T2.dfn[x]]++;
		x=T2.fth[x];
	}
}
void del(int x){
	w1[T2.dfn[x]]=0;
	while(x){
		w2[T2.dfn[x]]--;
		x=T2.fth[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+=x*w1[T2.dfn[x]]*w2[T2.dfn[x]];
		x=T2.fth[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){
		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);
			}
//			cout<<j<<":\n";
//			F(k,1,n) cout<<w1[T2.dfn[k]]<<' '<<w2[T2.dfn[i]]<<'\n';
			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
*/