#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define mat vector<vector<int>>
const int inf = 1 << 30;
const ll linf = 1e18;
const db EPS = 1e-7;
template<class T> void chmin(T& x, T y){if(x > y) x = y;}
template<class T> void chmax(T& x, T y){if(x < y) x = y;}

bool used[200001];
vector<int> G[200001];
vector<int> cycle;

int dfs(int p, int v){
    used[v] = true;
    for(auto u : G[v]){
        if(used[u] && u != p){
            cycle.push_back(v);
            return u;
        }
        if(!used[u]){
            int res = dfs(v, u);
            if(res != inf){
                if(res == 0) return 0;
                cycle.push_back(v);
                return (v == res ? 0 : res);
            }
        }
    }
    return inf;
}

void dfs2(int v, ll &cnt){
    used[v] = true;
    for(auto u : G[v]){
        if(!used[u]){
            cnt++;
            dfs2(u, cnt);
        }
    }
}

void solve(){
    ll n;
    cycle.clear();
    cin >> n;
    for(int i = 1; i <= n; i++){
        used[i] = false;
        G[i].clear();
    }

    for(int i = 1; i <= n; i++){
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    dfs(0, 1);
    for(int i = 1; i <= n; i++) used[i] = false;
    for(auto u : cycle) used[u] = true;
    ll cs = cycle.size();
    ll ans1 = n * (n - 1) / 2 + cs * (cs -  1) / 2;
    ll ans2 = 0;
    for(auto u : cycle){
        ll cnt = 0;
        dfs2(u, cnt);
        ans1 += cnt * (cs - 1);
        ans2 += cnt * (n - cnt - cs);
    }
    cout << ans1 + ans2 / 2 << endl;
    return;
}

int main(){
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}