#include <bits/stdc++.h>
#define int long long
using namespace std;
int head[300010];
int n = 0;
int m = 0;
int numEdge;
struct edge{
	int next;
	int to;
	int w;
}e[600010];
void AddEdge(int from, int to, int w){
	numEdge ++;
	e[numEdge].next = head[from];
	e[numEdge].to = to;
	e[numEdge].w = w;
	head[from] = numEdge;
}
int T = 0;
inline int read(){
     char ch=getchar();int x=0,f=1;
     while(ch<'0' || ch>'9')    {if(ch=='-')f=-1;ch=getchar();}
     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
     return x*f;
}
int siz[300010];
int son[300010];
int dep[300010];
int f[300010];
int anc[300010];//以全图中心为根，所有点属于的子树祖先 
int sec = 0;
int rt  = 0;
void getrt(int now, int fa){
	siz[now] = 1;
	for(int i = head[now]; i; i=  e[i].next){
		int nxt = e[i].to;
		if(nxt == fa){
			continue;
		}
		getrt(nxt, now);
		siz[now] += siz[nxt];
		if(siz[nxt] > siz[son[now]]){
			son[now] = nxt;
		}
	}
	if(siz[son[now]] * 2 <= n && (n - siz[now]) * 2 <= n){
		rt = now;
	}
}
void dfs(int now, int fa){
	siz[now] = 1;
	dep[now] = dep[fa] + 1;
	f[now] = fa;
	if(fa == rt){
		anc[now] = now;
	}
	else{
		anc[now] = anc[fa];
	}
	for(int i = head[now]; i; i=  e[i].next){
		int nxt = e[i].to;
		if(nxt == fa){
			continue;
		}
		dfs(nxt, now);
		siz[now] += siz[nxt];
		if(siz[nxt] > siz[son[now]]){
			if(now == rt){
				sec = son[rt];
			}
			son[now] = nxt;
		}
		else{//nxt 不是重儿子 
			if(siz[nxt] > siz[sec] && now == rt){
				sec = nxt;
			}
		}
	}
}
int op1[300010];
int op2[300010];
int op3[300010];
int y = 0;
void dfs1(int now, int fa){
	if(son[now] != 0){
		dfs1(son[now], now);
	}
	while(2 * siz[now] >= n - y && y > 0){
		op1[y] = now;
		y --;
	}
}
void dfs2(int now, int fa){
	if(now == rt){
		y = n;
		dfs2(sec, now);
	}
	else if(son[now] != 0){
		dfs2(son[now], now);
	}
	while(2 * siz[now] >= n - y && y > 0){
		op2[y] = now;
		y --;
	}
}
void dfs3(int now, int fa){
	if(son[now] != 0){
		dfs3(son[now], now);
	} 
	for(int i = head[now]; i; i = e[i].next){
		int nxt = e[i].to;
		if(nxt == fa || nxt == son[now] || dep[nxt] > dep[now]){
			continue;
		}
		dfs3(nxt, now);
	}
	int pos = 0;
	if(son[now] == 0){
		pos = now;
	}
	else{
		pos = op3[son[now]];
	}
	while(siz[pos] * 2 < siz[now]){
		pos = f[pos];
	}
	op3[now] = pos;
}
int ans = 0;
int uu[300010];
int vv[300010];
void solve(){
	for(int i = 1; i <= n; i++){
		int u = uu[i];
		int v = vv[i];
		if(dep[v] < dep[u]){//v在u上 
			swap(v, u);
		}
		int ptv = op3[v];
		ans += ptv;
		if(dep[f[ptv]] >= dep[v] && siz[son[f[ptv]]] * 2 <= siz[v] && (siz[v] - siz[son[f[ptv]]]) * 2 <= siz[v] && f[ptv] != 0){
			ans += f[ptv];
		}
		if(anc[v] == son[rt]){
			if(siz[son[rt]] - siz[v] >= siz[sec]){
				ans += rt;
			}
            else{
                ans += op2[siz[v]];
                if(f[op2[siz[v]]] == rt){
                	if(siz[son[f[op2[siz[v]]]]] * 2 <= n - siz[v]){
                		ans += f[op2[siz[v]]];
					}
				}
                else{
                	if(siz[son[f[op2[siz[v]]]]] * 2 <= n - siz[v] && (n - siz[v] - siz[son[f[op2[siz[v]]]]]) * 2 <= n - siz[v] && f[op2[siz[v]]] != 0){
                		ans += f[op2[siz[v]]];
					}
				}
            }
		}
		else{
			ans += op1[siz[v]];
			if(f[op1[siz[v]]] == rt){
            	if(siz[son[f[op1[siz[v]]]]] * 2 <= n - siz[v]){
               		ans += f[op1[siz[v]]];
				}
			}
            else{
               	if(siz[son[f[op1[siz[v]]]]] * 2 <= n - siz[v] && (n - siz[v] - siz[son[f[op1[siz[v]]]]]) * 2 <= n - siz[v] && f[op1[siz[v]]] != 0){
               		ans += f[op1[siz[v]]];
				}
			}
		}
	}
}
int q = 0;
signed main(){
	T = read();
	while(T -- ){
		sec = 0;
		ans = 0;
		rt = 0;
		numEdge = 0;
		for(int i = 1; i <= n; i++){
			son[i] = 0;
		}
		memset(e, 0, sizeof(e));
		memset(head, 0, sizeof(head));
		n = read();
		y = n;
		for(int i = 1; i < n; i++){
			int u = read();
			int v = read();
			AddEdge(u, v, 1);
			AddEdge(v, u, 1);
			uu[i] = u;
			vv[i] = v;
		}
		
		getrt(1, 0);
		for(int i = 1; i <= n; i++){
			son[i] = 0;
		}
		dfs(rt, 0);
		
		dfs1(rt, 0);
		
		dfs2(rt, 0);
		dfs3(rt, 0);
		solve();
		cout << ans << endl;
	}
	return 0;
}