#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 300005;
vector<vector<pii> > adj;
pii e[N];
int be;
bool v[N], ic[N];
int ca[N], cs, m, tt, sc;

void dfs1(int u){
    v[u] = 1;
    ca[cs ++] = u;
    for(pii& p : adj[u]){
        int vv = p.first, ei = p.second;
        if(!v[vv] && ei != be){
        	dfs1(vv);
		}
    }
}

int dfs2(int u, int fa){
    int sz = 1;
    for(pii& p : adj[u]){
        int w = p.first, ei = p.second;
        if(w == fa || ei == be || !ic[w]){
        	continue;
		}
        int sb = dfs2(w, u);
        sz += sb;
        m = max(m, sb);
    }
    tt = sz;
    return sz;
}

ll gs(){
    ll r = 0;
    for(int i = 0;i < cs;++ i){
        int u = ca[i];
        m = 0, tt = 0;
        dfs2(u, -1);
        m = max(m, sc - tt);
        if(m <= sc / 2) r += u;
    }
    return r;
}

void init(int n){
    adj.clear();
    adj.resize(n + 1);
    memset(v, 0, sizeof(v));
    memset(ic, 0, sizeof(ic));
    cs = 0;
}

int main(){
	freopen("centroid.in", "r", stdin);
	freopen("centroid.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T; cin >> T;
    while(T --){
        int n; cin >> n;
        init(n);
        for(int i = 0;i < n - 1;++ i){
            int u, vv; cin >> u >> vv;
            e[i] = {u, vv};
            adj[u].emplace_back(vv, i);
            adj[vv].emplace_back(u, i);
        }
        ll a = 0;
        for(int i = 0;i < n - 1;++ i){
            be = i;
            int u = e[i].first, vv = e[i].second;
            memset(v, 0, sizeof(v));
            cs = 0; dfs1(u); sc = cs;
            memset(ic, 0, sizeof(ic));
            for(int j = 0;j < cs;++ j){
            	ic[ca[j]] = 1;
			}
            a += gs();
            memset(v, 0, sizeof(v));
            cs = 0; dfs1(vv); sc = cs;
            memset(ic, 0, sizeof(ic));
            for(int j = 0;j < cs;++ j){
            	ic[ca[j]] = 1;
			}
            a += gs();
        }
        cout << a << '\n';
    }
    return 0;
}