#include <bits/stdc++.h>

const int bufsize = (1 << 20) + 10, N = 3e5 + 10;

inline char Getchar() {
    static char buf[bufsize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufsize, stdin), p1 == p2) ? EOF : *p1++;
}

inline int read() {
    int x = 0;
    char ch = Getchar();

    while (!isdigit(ch))
        ch = Getchar();

    while (isdigit(ch))
        x = x * 10 + ch - '0', ch = Getchar();

    return x;
}

int tot = 1, fir[N], nex[N << 1], got[N << 1];

inline void AddEdge(int u, int v) {
    nex[++tot] = fir[u], fir[u] = tot, got[tot] = v;
    nex[++tot] = fir[v], fir[v] = tot, got[tot] = u;
}

int rot = 0, siz[N], Max[N], son[N], par[N];
int idx = 0, dfn[N], b[N], w[N], p[N], a[N];

inline void dfs(int u, int fa, int n) {
    siz[u] = 1, Max[u] = 0;

    for (int i = fir[u]; i; i = nex[i])
        if (got[i] != fa)
            dfs(got[i], u, n), siz[u] += siz[got[i]], Max[u] = std::max(Max[u], siz[got[i]]);

    Max[u] = std::max(Max[u], n - siz[u]);

    if (!rot || Max[u] < Max[rot])
        rot = u;
}

inline void dfs(int u, int fa) {
    siz[u] = 1, Max[u] = son[u] = 0, par[u] = fa, dfn[u] = ++idx;

    for (int i = fir[u]; i; i = nex[i])
        if (got[i] != fa) {
            dfs(got[i], u), siz[u] += siz[got[i]];
            Max[u] = std::max(Max[u], siz[got[i]]);

            if (siz[got[i]] > siz[son[u]])
                son[u] = got[i];
        }

    if (siz[u] == 1)
        w[u] = u;
    else
        w[u] = w[son[u]];

    while (siz[u] - siz[w[u]] > siz[u] / 2)
        w[u] = par[w[u]];
}

int main() {
    freopen("centroid.in", "r", stdin);
    freopen("centroid.out", "w", stdout);
    int T = read();

    while (T--) {
        memset(fir, 0, sizeof(fir)), tot = 1;
        int n = read(), now = 0, cnt = 0, s = 0, tmp = 0;
        long long ans = 0;

        for (int i = 1; i <= n - 1; ++i)
            AddEdge(read(), read());

        idx = rot = 0, dfs(1, 0, n), dfs(rot, 0);
        auto check = [&](int u, int v) {
            return Max[v] <= siz[u] / 2;
        };
        auto Check = [&](int u, int v) {
            return Max[v] <= (n - siz[u]) / 2;
        };

        for (int i = 1; i <= n; ++i)
            if (i != rot)
                ans += w[i] + check(i, par[w[i]]) * par[w[i]];

        for (int now = rot; now; now = son[now])
            p[++cnt] = now;

        p[cnt + 1] = 0;

        for (int i = 1; i <= cnt; ++i)
            for (int j = siz[p[i + 1]] + 1; j <= siz[p[i]]; ++j)
                a[j] = p[i];

        for (int i = fir[rot]; i; i = nex[i])
            if (got[i] != son[rot] && siz[got[i]] > siz[s])
                s = got[i];

        cnt = 0, tmp = son[rot], son[rot] = s;

        for (int now = rot; now; now = son[now])
            p[++cnt] = now;

        p[cnt + 1] = 0;

        for (int i = 1; i <= cnt; ++i)
            for (int j = siz[p[i + 1]] + 1; j <= siz[p[i]]; ++j)
                b[j] = p[i];

        for (int i = 1; i <= n; ++i) {
            if (i == rot)
                continue;

            int w = (n - siz[i]) / 2 + ((n - siz[i]) & 1);

            if (dfn[tmp] <= dfn[i] && dfn[i] < dfn[tmp] + siz[tmp]) {
                ans += b[w] + (Check(i, par[b[w]]) || (par[b[w]] == rot && siz[s] <= (n - siz[i]) / 2)) * par[b[w]];
            } else
                ans += a[w] + Check(i, par[a[w]]) * par[a[w]];
        }

        printf("%lld\n", ans);
    }

    return 0;
}