#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 300000;
const int inf = (int)0x3f3f3f3f;

int T, n, ans, sum, rt, cnt;
int sz[N], son[N][2], f[N][20];
vector<int>v[N];

void update(int);
void dfs(int, int);
void get(int);
void dp(int, int);

signed main() {
	cin >> T;
	while(T--) {
		for(int i = 1; i <= n; i++) v[i].clear();
		for(int i = 1; i <= n; i++) {
			son[i][0] = son[i][1] = 0;
		}
		sum = 0;
		cin >> n;
		for(int i = 1; i < n; i++) {
			int x, y;
			cin >> x >> y;
			v[x].push_back(y);
			v[y].push_back(x);
		}
		dfs(1, 0);
		dp(1, 0);
		cout << sum << "\n";
	}
	return 0;
}
void update(int x) {
	f[x][0] = son[x][0];
	for (int i = 1; i <= 19; i++) {
		f[x][i] = f[f[x][i - 1]][i - 1];
	}
}
void dfs(int x, int frt) {
	sz[x] = 1;
	for(int i = 0; i < v[x].size(); i++) {
		int u = v[x][i];
		if(u == frt) continue;
		dfs(u, x);
		sz[x] += sz[u];
		if (sz[u] > sz[son[x][0]]) {
			son[x][1] = son[x][0];
			son[x][0] = u;
		}
		else if (sz[u] > sz[son[x][1]]) 
			son[x][1] = u;
	}
	update(x);
}
void get(int x) {
	int all = sz[x];
	for (int i = 19; i >= 0; i--) {
		if (sz[f[x][i]] > (all >> 1)){
			x = f[x][i];
		}
	}
	sum += x;
	if(all - sz[son[x][0]] <= (all >> 1)) ans += son[x][0];
}
void dp(int x, int fa) {
	int t1 = son[x][0], t2 = sz[x];
	for(int i = 0; i < v[x].size(); i++) {
		int u = v[x][i];
		if(u == fa) continue;
		if(u == t1) {
			son[x][0] = sz[son[x][1]] > n - t2 ? son[x][1] : fa;
		} else {
			son[x][0] = sz[t1] > n - t2 ? t1 : fa;
		}
		update(x);
		sz[x] = n - sz[u];
		get(x);
		get(u);
		dp(u, x);
	}
	son[x][0] = t1;
	sz[x] = t2;
	update(x);
}