// 私は猫です

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define uint unsigned
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define inf 1000000000
#define infll 1000000000000000000ll
#define pii pair<int,int>
#define rep(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define per(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define dF(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define cmh(sjy) while(sjy--)
#define lowbit(x) (x&(-x))
#define HH printf("\n")
#define eb emplace_back
#define poly vector<int>
#define SZ(x) ((int)x.size())
using namespace std;
ll read(){
	ll x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x*f;
}
namespace Fastio{struct Reader{template<typename T>Reader&operator>>(T&x){x=0;short f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();x*=f;return*this;}Reader&operator>>(double&x){x=0;double t=0;short f=1,s=0;char c=getchar();while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else{x*=f;return*this;}while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader&operator>>(long double&x){x=0;long double t=0;short f=1,s=0;char c=getchar();while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else{x*=f;return*this;}while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader&operator>>(__float128&x){x=0;__float128 t=0;short f=1,s=0;char c=getchar();while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else{x*=f;return*this;}while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader&operator>>(char&c){c=getchar();while(c==' '||c=='\n'||c=='\r')c=getchar();return*this;}Reader&operator>>(char*str){int len=0;char c=getchar();while(c==' '||c=='\n'||c=='\r')c=getchar();while(c!=' '&&c!='\n'&&c!='\r')str[len++]=c,c=getchar();str[len]='\0';return*this;}Reader&operator>>(string&str){str.clear();char c=getchar();while(c==' '||c=='\n'||c=='\r')c=getchar();while(c!=' '&&c!='\n'&&c!='\r')str.push_back(c),c=getchar();return*this;}Reader(){}}cin;const char endl='\n';struct Writer{const int Setprecision=6;typedef int mxdouble;template<typename T>Writer&operator<<(T x){if(x==0){putchar('0');return*this;}if(x<0)putchar('-'),x=-x;static short sta[40];short top=0;while(x>0)sta[++top]=x%10,x/=10;while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(double)_;static short sta[40];short top=0;while(_>0)sta[++top]=_%10,_/=10;if(top==0)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;putchar('.');for(int i=0;i<Setprecision;i++)x*=10;_=x;while(_>0)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(long double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(long double)_;static short sta[40];short top=0;while(_>0)sta[++top]=_%10,_/=10;if(top==0)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;putchar('.');for(int i=0;i<Setprecision;i++)x*=10;_=x;while(_>0)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(__float128 x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(__float128)_;static short sta[40];short top=0;while(_>0)sta[++top]=_%10,_/=10;if(top==0)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;putchar('.');for(int i=0;i<Setprecision;i++)x*=10;_=x;while(_>0)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(char c){putchar(c);return*this;}Writer&operator<<(char*str){int cur=0;while(str[cur])putchar(str[cur++]);return*this;}Writer&operator<<(const char*str){int cur=0;while(str[cur])putchar(str[cur++]);return*this;}Writer&operator<<(string str){int st=0,ed=str.size();while(st<ed)putchar(str[st++]);return*this;}Writer(){}}cout;}using namespace Fastio;
#define cin Fastio::cin
#define cout Fastio::cout
#define endl Fastio::endl
template<typename T>inline void chkmax(T &x,const T &y){ x=std::max(x,y); }
template<typename T>inline void chkmin(T &x,const T &y){ x=std::min(x,y); }
const int mod=998244353,maxn=100005;
namespace seg{
	#define ls (o<<1)
	#define rs (o<<1|1)
	uint tag[maxn<<2],t[maxn<<2],c[maxn<<2];
	void init(int n){ F(i,1,n<<2)tag[i]=t[i]=c[i]=0; }
	inline void maketag(int o,uint val){ tag[o]+=val,t[o]+=c[o]*val; }
	inline void pushdown(int o){ if(tag[o])maketag(ls,tag[o]),maketag(rs,tag[o]),tag[o]=0; }
	void update(int o,int l,int r,int ql,int qr,uint val){
		if(ql<=l&&qr>=r)return maketag(o,val),void();
		int mid=(l+r)>>1; pushdown(o);
		if(ql<=mid)update(ls,l,mid,ql,qr,val);
		if(qr>mid)update(rs,mid+1,r,ql,qr,val);
		t[o]=t[ls]+t[rs],c[o]=c[ls]+c[rs];
	}
	void change(int o,int l,int r,int pos,uint val){
		if(l==r)return c[o]=val,t[o]=val*tag[o],void();
		int mid=(l+r)>>1; pushdown(o);
		(pos<=mid)?change(ls,l,mid,pos,val):change(rs,mid+1,r,pos,val);
		t[o]=t[ls]+t[rs],c[o]=c[ls]+c[rs];	
	}
	uint query(int o,int l,int r,int ql,int qr){
		if(ql<=l&&qr>=r)return t[o];
		int mid=(l+r)>>1; pushdown(o);
		uint res=0;
		if(ql<=mid)res=query(ls,l,mid,ql,qr);
		if(qr>mid)res+=query(rs,mid+1,r,ql,qr);
		return res;
	}
}
vector<int>g[maxn];
int dsu[maxn],fa[maxn],top[maxn],dfn[maxn],n,tim,rev[maxn];
int find(int x){ return dsu[x]==x?x:dsu[x]=find(dsu[x]); }
struct Restruct_tree{
	vector<int>e[maxn];
	int siz[maxn],son[maxn],R;
	void dfs(int u){ 
		son[u]=0,siz[u]=1; 
		for(int v:e[u]){ 
			fa[v]=u,dfs(v); 
			if(siz[v]>siz[son[u]])son[u]=v; 
			siz[u]+=siz[v]; 
		}
	}
	void dfs1(int u,int t){
		rev[dfn[u]=++tim]=u,top[u]=t;
		if(!son[u])return;
		dfs1(son[u],t);
		for(int v:e[u])if(v^son[u])dfs1(v,v);
	}
	void add(int u,uint val){ for(;u;u=fa[top[u]])seg::update(1,1,n,dfn[top[u]],dfn[u],val); }
	uint query(int u){ uint R=0; for(;u;u=fa[top[u]])R+=seg::query(1,1,n,dfn[top[u]],dfn[u]); return R; }
	void init(int op){
		F(i,1,n)dsu[i]=i,e[i].clear(),fa[i]=0;
		if(op==0){
			F(u,1,n)for(int v:g[u])if(u>v)v=find(v),e[u].push_back(v),dsu[v]=u;
			dfs(n),dfs1(n,n);
		}else{
			dF(u,n,1)for(int v:g[u])if(u<v)v=find(v),e[u].push_back(v),dsu[v]=u;
			dfs(1);
		}
	}
}S,T;
void solve(){
	cin>>n,seg::init(n),tim=0;
	F(i,1,n)g[i].clear();
	F(i,1,n-1){
		int u,v; cin>>u>>v;
		g[u].push_back(v),g[v].push_back(u);
	}
	auto add=[&](int u,uint val){
		T.add(u,val);
		seg::change(1,1,n,dfn[u],val==1?u:0);
	};
	auto dfs2=[&](auto &self,int u,int val)->void{
		add(u,val);
		for(int v:S.e[u])self(self,v,val);
	};
	uint ans=0;
	auto DFS=[&](auto &self,int u)->void{
		if(!u)return;
		for(int v:S.e[u])if(v^S.son[u])self(self,v),dfs2(dfs2,v,-1);
		if(S.son[u])self(self,S.son[u]);
		for(int v:S.e[u])if(v^S.son[u])dfs2(dfs2,v,1);
		add(u,1);
		ans+=u*T.query(u);
	};
	S.init(1),T.init(0),DFS(DFS,1);
	cout<<ans<<endl;
}
signed main(){
	// ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int zsy=1; cin>>zsy;
	F(____,1,zsy)solve();
}