#include <bits/stdc++.h>

using i64 = long long;

template <typename T> struct Fenwick {
    int n; std::vector<T> a;
    Fenwick(int n = 0) { init(n); }
    void init(int m) { n = m, a.assign(n, T()); }
    void add(int p, const T &x) {
        for (++p; p <= n; p += p & -p) a[p - 1] += x;
    }
    T sum(int p) const {
        auto x = T(); for (; p; p -= p & -p) x += a[p - 1];
        return x;
    }
    T rangeSum(int l, int r) const { return sum(r) - sum(l); }
};

void solve() {
    int n; std::cin >> n;
    std::vector<std::vector<int>> adj(n);
    for (int i = 0; i < n - 1; ++i) {
        int u, v; std::cin >> u >> v, --u, --v;
        adj[u].push_back(v), adj[v].push_back(u);
    }

    std::vector<int> sz(n, 1), fa(n, -1);
    auto dfs1 = [&](auto self, int u) -> void {
        for (auto v : adj[u]) if (v != fa[u])
            fa[v] = u, self(self, v), sz[u] += sz[v];
    };
    dfs1(dfs1, 0);

    Fenwick<int> fen0(n), fen1(n);
    for (int i = 0; i < n; ++i) fen1.add(sz[i] - 1, 1);

    i64 ans = 0;
    auto dfs2 = [&](auto self, int u) -> void {
        std::multiset<int> s{0};
        for (auto v : adj[u]) s.insert(v == fa[u] ? n - sz[u] : sz[v]);

        auto get = [&](int x) {
            auto it = std::prev(s.end()); if (*it == x) --it;
            return std::pair{std::max(2 * x - n, 1) - 1, std::max(n - 2 * *it, 0)};
        };

        int sum = 0;
        auto [L, R] = get(n - sz[u]); int X = fen0.rangeSum(L, R);
        for (auto v : adj[u]) if (v != fa[u]) {
            auto [l, r] = get(sz[v]); int x = fen0.rangeSum(l, r);

            fen1.add(sz[u] - 1, -1), fen1.add(n - sz[v] - 1, 1);
            self(self, v);
            fen1.add(n - sz[v] - 1, -1), fen1.add(sz[u] - 1, 1);

            if (l < r) sum += fen0.rangeSum(l, r) - x;
        }
        fen0.add(sz[u] - 1, 1);
        if (L < R) sum += fen1.rangeSum(L, R) - (fen0.rangeSum(L, R) - X);

        ans += 1ll * sum * (u + 1);
    };
    dfs2(dfs2, 0);

    std::cout << ans << '\n';
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int t; std::cin >> t;
    while (t--) solve();

    return 0;
}