#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout << (#x) << " is " << (x) << endl
#define debug cout << "hi" << endl
#define maxn 3e5+50

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long ,long long>pll;

ll gcd(ll a, ll b) {return (!b ? a : gcd(b, a % b));}
ll lcm(ll a, ll b) {return ((a*b)/gcd(a,b));}

const ll mod = 1e9 + 7;
const ll MOD = 998244353;
const int INF32 = 1<<30;
const ll INF64 = 1LL<<60;
const ld pi = 3.141592653589793;

 long long modpow(long long n, long long k,long long mod)
{
if (k == 0) return 1;
long long r = modpow(n * n % mod, k >> 1, mod);
if (k & 1) r = r * n % mod;
return r;
}

void solve(){
    int t;cin >> t;
    while(t--){
        int n;cin >> n;
        vector<vector<int>>g(n);
        queue<int>leaf;
        vector<int>val(n,1);
        for(int i = 0;i<n;i++)
        {
            int v,u;cin >> v >> u;
            v--;u--;
            g[v].push_back(u);
            g[u].push_back(v);
        }
        for(int i = 0;i<n;i++){
            if(g[i].size()==1) leaf.push(i);
        }
        while(!leaf.empty()){
            int u = leaf.front();leaf.pop();
            int v = g[u][0];
            val[v] += val[u];
            val[u] = 0;
            g[u].clear();
            g[v].erase(find(g[v].begin(),g[v].end(),u));
            if(g[v].size()==1){
                leaf.push(v);
            }
        }
        ll ans = 0;
        for(int i = 0;i<n;i++){
            ans += 1ll*val[i]*(val[i]-1)/2;
            ans += 1ll*val[i]*(n-val[i]);
        }
        cout << ans <<endl;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    solve();
    return 0;
}
