#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+5;
int n;
vector<int> edg[N];
int tag[N<<2];
struct node{
	int mn,cnt;
	node(int a=0,int b=0):mn(a),cnt(b){}
	node operator+(node a)
	{
		node res;
		res.mn=min(mn,a.mn);
		if(mn==res.mn) res.cnt+=cnt;
		if(res.mn==a.mn) res.cnt+=a.cnt;
		return res;
	}
}v[N<<2];
void push_down(int idx)
{
	if(!tag[idx]) return;
	v[idx<<1].mn+=tag[idx];
	tag[idx<<1]+=tag[idx];
	
	v[idx<<1|1].mn+=tag[idx];
	tag[idx<<1|1]+=tag[idx];
	tag[idx]=0;
}
void add(int l,int r,int tl,int tr,int vv,int idx)
{
	if(l>=tl&&r<=tr)
	{
		v[idx].mn+=vv;
		tag[idx]+=vv;
		return;
	}
	push_down(idx);
	int mid=(l+r)>>1;
	if(mid>=tl) add(l,mid,tl,tr,vv,idx<<1);
	if(mid<tr) add(mid+1,r,tl,tr,vv,idx<<1|1);
	v[idx]=v[idx<<1]+v[idx<<1|1];
}
node query(int l,int r,int tl,int tr,int idx)
{
	if(l>=tl&&r<=tr) return v[idx];
	push_down(idx);
	int mid=(l+r)>>1;
	if(mid>=tr) return query(l,mid,tl,tr,idx<<1);
	else if(mid<tl) return query(mid+1,r,tl,tr,idx<<1|1);
	else return query(l,mid,tl,tr,idx<<1)+query(mid+1,r,tl,tr,idx<<1|1);
}
void sol()
{
	scanf("%d",&n);
	int i,j,k;	
	for(i=1;i<=n;i++) edg[i].clear();
	for(i=1;i<n;i++)
	{
		scanf("%d%d",&j,&k);
		edg[j].push_back(k);
		edg[k].push_back(j);
	}
	for(i=1;i<=4*n;i++) v[i].mn=0,v[i].cnt=1,tag[i]=0;
	ll ans=0;
	for(i=1;i<=n;i++)
	{
		add(1,n,1,i,1,1);
		for(int to:edg[i])
			if(to<i) add(1,n,1,to,-1,1);
		ans+=query(1,n,1,i,1).cnt;
	}
	printf("%lld\n",ans);
	return;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t)
	{
		--t;
		sol();
	}
	return 0;
}
/*
枚举 r
考虑维护一个数组 f[i] 表示 i 作为左端点是否合法
当前考虑 x 作为右端点
先让 f[1]~f[i] 均 +1
考虑所有边 (x,y),满足 y<x
令 f[1]~f[y] 均 -1
当 f[i]=1 时，该点作为左端点合法
因为结构是一棵树 所以可以依次将编号小的向编号大的合并，不会成环
*/