#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;

void dfs(ll u, vector<vector<ll>>& adj, vector<bool>& visited, vector<ll>& deg, queue<ll>& leaves){
    deg[u] = adj[u].size();
    if(deg[u] == 1)
        leaves.push(u);
    visited[u] = true;
    for(auto it : adj[u]){
        if(!visited[it])
            dfs(it, adj, visited, deg, leaves);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    ll t;
    cin >> t;

    while(t--){
        ll n;
        cin >> n;
        
        vector<ll> cnt(n, 1);
        vector<vector<ll>> adj(n);
        for(ll i=0; i<n; i++){
            ll u, v;
            cin >> u >> v;
            --u; --v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }

        vector<bool> visited(n, false);
        vector<ll> deg(n);
        queue<ll> leaves;

        dfs(0, adj, visited, deg, leaves);

        while(!leaves.empty()){
            ll leaf = leaves.front();
            leaves.pop();

            ll par;
            for(auto it : adj[leaf])
                if(deg[it] > 1)
                    par = it;
    
            cnt[par] += cnt[leaf];
            cnt[leaf] = -1;
            deg[leaf]--; deg[par]--;

            if(deg[par]==1)
                leaves.push(par);
        }

        ll ans = 0ll;
        for(ll i=0; i<n; i++){
            if(cnt[i] == -1)
                continue;
            
            ans = 1ll*ans + (cnt[i] * (cnt[i]-1))/2 + cnt[i]*(n-cnt[i]);
        }

        // for(int i=1; i<=n; i++)
        //     cout << i <<  '\t';
        // cout << '\n';

        // for(int i=0; i<n; i++)
        //     cout << cnt[i] << '\t';
        // cout << '\n';

        // for(int i=0; i<n; i++)
        //     cout << deg[i] << '\t';

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